Кратчайший путь в списке смежности в невзвешенном графе

Question

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

AdjList - это ArrayList, где каждый элемент является объектом.Каждый объект содержит ArrayList внутри для представления связанных вершин.Так, например, на изображении выше Vertext 1 (первый индекс в AdjList) связан с вершиной в индексах 2, 4 и 5 в AdjList.Является ли это представление списка смежности правильным?(ps: я знаю, что индексы начинаются с 0, я поставил 1 здесь для простоты / легкости).

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

Answer 1

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

1. Алгоритм Дейкстры , чтобы найти кратчайший путь между одной вершиной и всеми остальными (а затем выбрать ту, которая вам нужна).
2. Алгоритм Роя-Флойда для нахождения кратчайшего пути между всеми возможными парами вершин.

Ссылки также включают псевдокод.

Answer 2

Вот пример алгоритма кратчайшего пути Дейкстры в Java вместе с пояснениями

Answer 3

Вы можете использовать Dijkstra's и Floyd Warshall.Для невзвешенного графика примем вес каждого ребра равным 1 и применим алгоритм.