Dijkstra's Algorithm in Python 3

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)]

    def add_edge(self, source, dest, weight):
        assert source < self.vertex_count
        assert dest < self.vertex_count
        self.adjacency_list[source].append(Edge(dest, weight))
        self.adjacency_list[dest].append(Edge(source, weight))

    def get_edge(self, vertex):
        for e in self.adjacency_list[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[1]

        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)
    g.add_edge(0, 1, 4)
    g.add_edge(1, 7, 6)
    g.add_edge(1, 2, 1)
    g.add_edge(2, 3, 3)
    g.add_edge(3, 7, 1)
    g.add_edge(3, 4, 2)
    g.add_edge(3, 5, 1)
    g.add_edge(4, 5, 1)
    g.add_edge(5, 6, 1)
    g.add_edge(6, 7, 2)
    g.add_edge(6, 8, 2)
    g.add_edge(7, 8, 2)
    # for testing negative cycles
    # g.add_edge(1, 9, -5)
    # g.add_edge(9, 7, -4)

    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 == [1] and distance == 0


if __name__ == "__main__":  
    main()

This was my work in progress.

whiteboard Dijkstra's algorithm for single source shortest paths

Article originally appeared here on my other blog.

comments powered by Disqus