Dijkstra's algorithm: Difference between revisions
m
→{{header|Julia}}: update for 1.x
m (→{{header|ATS}}) |
m (→{{header|Julia}}: update for 1.x) |
||
Line 4,032:
=={{header|Julia}}==
{{works with|Julia|
<syntaxhighlight lang="julia">
struct Digraph{T <: Real,U}
edges::Dict{Tuple{U,U},T}
verts::Set{U}
Line 4,083 ⟶ 4,085:
else
while dest != source
dest = prev[dest]
end
return rst, cost
end
Line 4,092 ⟶ 4,094:
# testgraph = [("a", "b", 1), ("b", "e", 2), ("a", "e", 4)]
const testgraph = [("a", "b", 7), ("a", "c", 9), ("a", "f", 14), ("b", "c", 10),
("b", "d", 15), ("c", "d", 11), ("c", "f", 2), ("d", "e", 6),
("e", "f", 9)]
g = Digraph(testgraph)▼
src, dst = "a", "e"▼
path, cost = dijkstrapath(g, src, dst)▼
println("Shortest path from $src to $dst: ", isempty(path) ? "no possible path" : join(path, " → "), " (cost $cost)")▼
function testpaths()
# Print all possible paths▼
▲ g = Digraph(testgraph)
@printf("\n%4s | %3s | %s\n", "src", "dst", "path")▼
▲ src, dst = "a", "e"
@printf("----------------\n")▼
for src in vertices(g), dst in vertices(g)▼
path, cost = dijkstrapath(g, src, dst)
▲ # Print all possible paths
end</syntaxhighlight>▼
▲ @printf("\n%4s | %3s | %s\n", "src", "dst", "path")
▲ @printf("----------------\n")
▲ for src in vertices(g), dst in vertices(g)
▲ path, cost = dijkstrapath(g, src, dst)
▲
end
end
<pre>Shortest path from a to e: a → c → d → e (cost 26)
| |||