Блог

Алгоритмы поиска путей, такие как A*, на 100% гарантируют кратчайший путь. Но можем ли мы вручную проанализировать, является ли данный путь в графике кратчайшим путем?

Предположим, что у нас есть этот взвешенный график, Взвешенный график

Предположим, что наш начальный узел-УЗЕЛ 1, и мы хотим перейти к УЗЛУ 2. Путь, который мы выбрали, — это узел 1 — > узел 2. Очевидно, что это самый короткий путь. Как мы можем вручную доказать или определить, является ли этот путь кратчайшим путем без каких-либо компьютеров?

Можно воспользоваться Dijkstra алгоритмом, чтобы найти кратчайший путь.