|
|
| (не показано 5 промежуточных версий 3 участников) |
| Строка 1: |
Строка 1: |
| − | Алгоритм Дейкстры (Dijkstra) предназначен для решения задачи [[Поиск кратчайших путей в графе]].
| + | #REDIRECT [[discopal:{{PAGENAME}}]] |
| − | | + | |
| − | Важным фактом, позволяющим исключить перебор, является то, что если у нас есть кратчайший путь от ''v'' до ''w'', проходящий через вершину ''y'', назовем его <math>(v \rightarrow w)^*</math>, то его первая часть от ''v'' до ''y'', <math>(v \rightarrow y)^*</math>, тоже будет кратчайшим путем. Действительно, если бы это было не так, т.е. существовал бы путь <math>(v \rightarrow y)^!</math> длины меньшей, чем <math>(v \rightarrow y)^*</math>, то можно было бы улучшить оптимальный путь <math>(v \rightarrow w)^*</math>, заменив в нем <math>(v \rightarrow y)^*</math> на <math>(v \rightarrow y)^!</math>.
| + | |
| − | | + | |
| − | В алгоритме Дейкстры, мы, итерационно поддерживаем два множества вершин:
| + | |
| − | | + | |
| − | ;Visited: множество вершин, до которых мы уже нашли кратчайший путь, ассоциированных со стоимостями кратчайших путей от стартовой вершины до них.
| + | |
| − | ;ToVisit: множество вершин, которые достижимы одним ребром из множества вершин ''Visited'', ассоциированных с верхними оценками стоимости пути до них.
| + | |
| − | | + | |
| − | На каждой итерации, мы выбираем из достижимых вершин вершину ''v'', самую ближайшую к стартовой вершине ''s'', и переносим ее из множества ''ToVisit'' в множество ''Visited'', увеличиваем множество «кандидатов» ''ToVisit'' ее соседями, и пересчитываем верхнюю оценку удаленности вершин из ''ToVisit'' до вершины ''s''.
| + | |
| − | | + | |
| − | В иллюстрации выполнения алгоритма, мы показываем изменение на каждой итерации хэш-таблиц ''Visited'' и ''ToVisit'', а в конце изображен входной граф, где сплошными линиями нарисованы имеющиеся ребра с ассоциированными длинами, а пунктиром — найденные кратчайшие пути.
| + | |
| − | | + | |
| − | Важно, что алгоритм работоспособен только в случае положительных расстояний, в противном случае, можно попробовать использовать [[алгоритм Флойда-Уоршолла]].
| + | |
| − | | + | |
| − | Код алгоритма, представлен в виде функции на языке [[Python]].
| + | |
| − | | + | |
| − | <code-python>
| + | |
| − | # Находит кратчайшие пути из одной вершины | + | |
| − | # во все остальные.
| + | |
| − | def dijkstra(G,s):
| + | |
| − | print "StartVertice:",s
| + | |
| − | # хэш-таблица вершин, до которых построены кратчайшие пути, (узел:стоимость)
| + | |
| − | Visited={}
| + | |
| − | # хэш-таблица вершин, до которых еще не построены кратчайшие пути, (узел:стоимость)
| + | |
| − | ToVisit={s:0}
| + | |
| − | Paths = {s:[s]} # хэш-таблица (узел:кратчайший путь)
| + | |
| − | while ToVisit: # пока есть вершины, до которых не построен кратчайший путь
| + | |
| − | print Visited, ToVisit, "-------->",
| + | |
| − | v=argmin(ToVisit) # выбираем ближайшую
| + | |
| − | Visited[v]=ToVisit[v]; del ToVisit[v]; # считаем, что до нее кратчайший путь найден
| + | |
| − | for w in G.neighbors(v): # для всех соседей вершины $v$
| + | |
| − | if (w not in Visited): # к которым еще не нашли кратчайший путь
| + | |
| − | vwLength = Visited[v] + G.get_edge(v,w) # обновляем кратчайшие пути
| + | |
| − | if (w not in ToVisit) or (vwLength < ToVisit[w]):
| + | |
| − | ToVisit[w] = vwLength
| + | |
| − | Paths[w] = Paths[v]+[w]
| + | |
| − | print Visited, ToVisit
| + | |
| − | print Visited, Paths
| + | |
| − | return (Visited,Paths)
| + | |
| − | </code-python>
| + | |
| − | | + | |
| − | StartVertice: 2
| + | |
| − | {} {2: 0} --------> {2: 0} {1: 15, 3: 20, 4: 15}
| + | |
| − | {2: 0} {1: 15, 3: 20, 4: 15} --------> {1: 15, 2: 0} {0: 75, 3: 20, 4: 15}
| + | |
| − | {1: 15, 2: 0} {0: 75, 3: 20, 4: 15} --------> {1: 15, 2: 0, 4: 15} {0: 75, 3: 20}
| + | |
| − | {1: 15, 2: 0, 4: 15} {0: 75, 3: 20} --------> {1: 15, 2: 0, 3: 20, 4: 15} {0: 70}
| + | |
| − | {1: 15, 2: 0, 3: 20, 4: 15} {0: 70} --------> {0: 70, 1: 15, 2: 0, 3: 20, 4: 15} {}
| + | |
| − | {0: 70, 1: 15, 2: 0, 3: 20, 4: 15} {0: [2, 3, 0], 1: [2, 1], 2: [2], 3: [2, 3], 4: [2, 4]}
| + | |
| − | | + | |
| − | <graph>
| + | |
| − | graph G{ rankdir=TB;
| + | |
| − | 0 [label="NY(0)"];
| + | |
| − | 1 [label="Moscow(1)"];
| + | |
| − | 2 [label="Minsk(2)"];
| + | |
| − | 3 [label="Berlin(3)"];
| + | |
| − | 4 [label="Kiev(4)"];
| + | |
| − | 0 -- 1[fontcolor="blue",label="$60",style=solid];
| + | |
| − | 0 -- 3[fontcolor="blue",label="$50",style=solid];
| + | |
| − | 0 -- 4[fontcolor="blue",label="$80",style=solid];
| + | |
| − | 1 -- 2[fontcolor="blue",label="$15",style=solid];
| + | |
| − | 1 -- 3[fontcolor="blue",label="$50",style=solid];
| + | |
| − | 1 -- 4[fontcolor="blue",label="$10",style=solid];
| + | |
| − | 2 -- 3[fontcolor="blue",label="$20",style=solid];
| + | |
| − | 2 -- 4[fontcolor="blue",label="$15",style=solid];
| + | |
| − | 3 -- 4[fontcolor="blue",label="$30",style=solid];
| + | |
| − | 2 -- 3 -- 0 [fontcolor="red",label="Minsk-NY",style=dashed];
| + | |
| − | 2 -- 1 [fontcolor="red",label="Minsk-Moscow",style=dashed];
| + | |
| − | 2 -- 3 [fontcolor="red",label="Minsk-Berlin",style=dashed];
| + | |
| − | 2 -- 4 [fontcolor="red",label="Minsk-Kiev",style=dashed];
| + | |
| − | }
| + | |
| − | </graph>
| + | |
| − | | + | |
| − | | + | |
| − | | + | |
| − | | + | |
| − | | + | |
| − | [[Category:Алгоритмы]]
| + | |
| − | | + | |
| − | {{replicate-from-custiswiki-to-lib}}
| + | |
