Самый короткий путь между двумя вершинами в графе

Question

Мне нужно выполнить следующую задачу: «У вас есть граф G (V, E) и его вершины x и y. Напишите программу, которая находит кратчайший путь между двумя вершинами , по числу вершин.

Я не понимаю, зависит ли это от меня, чтобы решить, включен ли этот график или нет, или должен ли я иметь класс ребер или какую визуальную графу выполнить. упражнения в главе «Деревья и графики» моей книги (Введение в программирование с помощью java), и я не знаю с чего начать. Как вы это сделаете и почему?

Answer 1

Вы ищете алгоритм Дейкстры. дать вам кратчайший путь на любом график между двумя точками, чтобы использовать этот алгоритм, вам нужно будет знать, как использовать сами графики и очереди приоритетов. В Википедии есть очень хорошая статья об алгоритме.

Answer 2

Поскольку не сказано, что оно направлено в вопрос, тогда предположим, что оно неориентировано. Также они хотят, чтобы вы нашли кратчайший путь по количеству вершин, поэтому он также невзвешен. Предположим, что он неориентирован и невзвешен.

Например - N - число вершин, М - число ребер

4 5 
1 2 
2 3 
3 4 
1 3 
2 4 

Для представления графа либо использовать матрицу смежности (простейшие один) или список смежности. Матрица смежности является двумерным массивом G, где G [a] [b] истинна, когда есть ребро между a и b и false в противном случае.