37 lines
784 B
Text
37 lines
784 B
Text
|
F dijkstra(graph, source)
|
|||
|
|
V n = graph.len
|
|||
|
|
V dist = [Float.infinity] * n
|
|||
|
|
V previous = [-1] * n
|
|||
|
|
dist[source] = 0
|
|||
|
|
V Q = Array(0 .< n)
|
|||
|
|
L !Q.empty
|
|||
|
|
V u = min(Q, key' n -> @dist[n])
|
|||
|
|
Q.remove(u)
|
|||
|
|
I dist[u] == Float.infinity
|
|||
|
|
L.break
|
|||
|
|
L(v) 0 .< n
|
|||
|
|
I graph[u][v] & (v C Q)
|
|||
|
|
V alt = dist[u] + graph[u][v]
|
|||
|
|
I alt < dist[v]
|
|||
|
|
dist[v] = alt
|
|||
|
|
previous[v] = u
|
|||
|
|
R previous
|
|||
|
|
|
|||
|
|
F display_solution(predecessor)
|
|||
|
|
V cell = predecessor.len - 1
|
|||
|
|
L cell != 0
|
|||
|
|
print(cell, end' ‘<’)
|
|||
|
|
cell = predecessor[cell]
|
|||
|
|
print(0)
|
|||
|
|
|
|||
|
|
V graph = [
|
|||
|
|
[0,1,0,0,0,0],
|
|||
|
|
[1,0,1,0,1,0],
|
|||
|
|
[0,1,0,0,0,1],
|
|||
|
|
[0,0,0,0,1,0],
|
|||
|
|
[0,1,0,1,0,0],
|
|||
|
|
[0,0,1,0,0,0]
|
|||
|
|
]
|
|||
|
|
|
|||
|
|
display_solution(dijkstra(graph, 0))
|