51 lines
1.5 KiB
Text
51 lines
1.5 KiB
Text
T Edge
|
||
String start
|
||
String end
|
||
Int cost
|
||
|
||
F (start, end, cost)
|
||
.start = start
|
||
.end = end
|
||
.cost = cost
|
||
|
||
T Graph
|
||
[Edge] edges
|
||
Set[String] vertices
|
||
|
||
F (edges)
|
||
.edges = edges.map((s, e, c) -> Edge(s, e, c))
|
||
.vertices = Set(.edges.map(e -> e.start)).union(Set(.edges.map(e -> e.end)))
|
||
|
||
F dijkstra(source, dest)
|
||
assert(source C .vertices)
|
||
V dist = Dict(.vertices, vertex -> (vertex, Float.infinity))
|
||
V previous = Dict(.vertices, vertex -> (vertex, ‘’))
|
||
dist[source] = 0
|
||
V q = copy(.vertices)
|
||
V neighbours = Dict(.vertices, vertex -> (vertex, [(String, Int)]()))
|
||
L(start, end, cost) .edges
|
||
neighbours[start].append((end, cost))
|
||
|
||
L !q.empty
|
||
V u = min(q, key' vertex -> @dist[vertex])
|
||
q.remove(u)
|
||
I dist[u] == Float.infinity | u == dest
|
||
L.break
|
||
L(v, cost) neighbours[u]
|
||
V alt = dist[u] + cost
|
||
I alt < dist[v]
|
||
dist[v] = alt
|
||
previous[v] = u
|
||
|
||
Deque[String] s
|
||
V u = dest
|
||
L previous[u] != ‘’
|
||
s.append_left(u)
|
||
u = previous[u]
|
||
s.append_left(u)
|
||
R s
|
||
|
||
V graph = Graph([(‘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)])
|
||
print(graph.dijkstra(‘a’, ‘e’))
|