36 lines
784 B
Text
36 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))
|