Число Бейкона и Графы

[grich]

1969 год

[andy_p]

Алгори́тм Де́йкстры (англ. Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных.

[TenMozes]

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

[andy_p]

У вас взвешенный граф с весами равными единице.
Так что, алгоритм Дейкстры вполне себе работает.
И да, алгоритм Дейкстры — это bfs.

[andy_p]

Единственное отличие в том, что в алгоритме Дейкстры
используется приоритетным очередь, а у вас обычная.
Если говорить про оптимизацию, то тогда надо смотреть
на алгоритм топологической сортировки.