Greed is good. And Dijkstra's algorithm is greedy.

Dijkstra's algorithm not only calculates the shortest (lowest weight) path on a graph from source vertex S to destination V, but also calculates the shortest path from S to every other vertex.

My implementation in Python doesn't return the shortest paths to all vertices, but it could. It returns the shortest path from source to destination, and the sum of the weights along that path.

It uses a thread-safe priority queue (min-heap heapq behind the scenes) from the Queue library: https://docs.python.org/3.5/library/queue.html#module-queue

``````import queue
from collections import namedtuple

Edge = namedtuple('Edge', ['vertex', 'weight'])

class GraphUndirectedWeighted(object):
def __init__(self, vertex_count):
self.vertex_count = vertex_count
self.adjacency_list = [[] for _ in range(vertex_count)]

assert source < self.vertex_count
assert dest < self.vertex_count

def get_edge(self, vertex):
yield e

def get_vertex(self):
for v in range(self.vertex_count):
yield v

def dijkstra(graph, source, dest):
q = queue.PriorityQueue()
parents = []
distances = []
start_weight = float("inf")

for i in graph.get_vertex():
weight = start_weight
if source == i:
weight = 0
distances.append(weight)
parents.append(None)

q.put(([0, source]))

while not q.empty():
v_tuple = q.get()
v = v_tuple

for e in graph.get_edge(v):
candidate_distance = distances[v] + e.weight
if distances[e.vertex] > candidate_distance:
distances[e.vertex] = candidate_distance
parents[e.vertex] = v
# primitive but effective negative cycle detection
if candidate_distance < -1000:
raise Exception("Negative cycle detected")
q.put(([distances[e.vertex], e.vertex]))

shortest_path = []
end = dest
while end is not None:
shortest_path.append(end)
end = parents[end]

shortest_path.reverse()

return shortest_path, distances[dest]

def main():
g = GraphUndirectedWeighted(9)
# for testing negative cycles

shortest_path, distance = dijkstra(g, 0, 1)
assert shortest_path == [0, 1] and distance == 4

shortest_path, distance = dijkstra(g, 0, 8)
assert shortest_path == [0, 1, 2, 3, 7, 8] and distance == 11

shortest_path, distance = dijkstra(g, 5, 0)
assert shortest_path == [5, 3, 2, 1, 0] and distance == 9

shortest_path, distance = dijkstra(g, 1, 1)
assert shortest_path ==  and distance == 0

if __name__ == "__main__":
main()
``````