Поясните пожалуста Алгоритм Дейкстры

← →
NoDt (2008-11-17 23:04) [0]

Предположим у нас есть массив
-1 -1 -1 -1 -1
10 -1 -1 -1 -1
-1 50 -1 20 -1
30 -1 -1 -1 -1
90 -1 15 60 -1

Где -1 означает что связи между вершинами графа нет.

Получаем массив веса вершин

-1 10 -1 30 90
-1 -1 60 -1 -1
-1 -1 -1 -1 75
-1 -1 50 -1 -1

Следовательно Кратчайшей путь от 1 до 2:10, 3:50, 4:30, 5:75

А как Получить саму последовательность кротчайшего пути? (В данном примере это 1, 4,3,5)

← →
Kerk © (2008-11-17 23:26) [1]

Ты как-то не так алгоритм применяешь. На самом деле в результирующей матрице должна быть не длина пути, а номер следующей вершины. (это если мне память не изменила)

почитай
http://algolist.manual.ru/maths/graphs/shortpath/dijkstra.php

← →
TUser © (2008-11-18 10:44) [2]

У Дейкстры вообще несколько алгоритмов. Получить кратчайший путь:

1. Mark all vertexes as FALSE 2. Mark Start as TRUE 3. for the every Vertex do 4. nearest := none; score := MaxInt; 5. for the every Vertex (as A) do 7. if it is TRUE then 8. for the every Vertex (as B) do 9. if it is FALSE then 10. if there is an edge from A to B then 11. if the weght of this edge < score then 12. Mark B as true 13. Mark that the way to B is from A 14. way is empty 15. current_mode is finish 16. while current_mode is not Start do 17. put the current mode to the end of the way 18. current_mode := the marked way to the current_mode // like A for B in the line 13

← →
@!!ex © (2008-11-18 11:17) [3]

Я для поиска пути использую волновой алгоритм с модицикациями. Просто и сердито.

> 17. put the current mode to the end of the way

имеется ввиду, что оно растет с конца, дабавляется-то как раз в начало :)

наврал, конечно, на каждом шаге цикла из 3 надо найти только одно новое ребро, типа

3. for the every Vertex do 4. nearest := none; score := MaxInt; 5. for the every Vertex (as A) do 7. if it is TRUE then 8. for the every Vertex (as B) do 9. if it is FALSE then 10. if there is an edge from A to B then 11. if the weght of this edge < score then 11a. score = this wieght 11b. nearest := A and B 12. Mark nearest.B as true 13. Mark that the way to nearest.B is from nearest.A

Поясните пожалуста Алгоритм Дейкстры Найти похожие ветки