Anonymous user
Dijkstra's algorithm: Difference between revisions
Fix wrong python code
No edit summary |
(Fix wrong python code) |
||
Line 3,732:
<lang python>from collections import namedtuple, deque
from pprint import pprint as pp
inf = float('inf')
Edge = namedtuple('Edge', ['start', 'end', 'cost'])
class Graph():
def __init__(self, edges):
self.edges
# print(dir(self.
self.vertices = {e.start for e in self.edges} | {e.end for e in self.edges}
def dijkstra(self, source, dest):
assert source in self.vertices
Line 3,752 ⟶ 3,753:
neighbours[start].add((end, cost))
#pp(neighbours)
while q:
# pp(q)
u = min(q, key=lambda vertex: dist[vertex])
q.remove(u)
Line 3,770 ⟶ 3,772:
s.appendleft(u)
return s
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),
Line 3,778 ⟶ 3,780:
{{out}}
<pre>deque(['a', 'c', 'd', 'e'])</pre>
=={{header|Racket}}==
| |||