Скачать: CL | DM;

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

← →
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]

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

---

← →
TUser ©   (2008-11-18 12:24) [4]

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

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

---

← →
TUser ©   (2008-11-18 15:53) [5]

наврал, конечно, на каждом шаге цикла из 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


---

Страницы: 1 вся ветка

Скачать: CL | DM;



Память: 0.46 MB
Время: 0.011 c