2024-07-13 15:19:22 -07:00
|
|
|
|
T Edge = (String start, String end, Int cost)
|
2023-07-01 11:58:00 -04:00
|
|
|
|
|
|
|
|
|
|
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’))
|
