Python Tutorial

Monday, October 19, 2015

Dijkstra algorithm


Dijkstra algorithm is a single source shortest path algorithm. For a given source node in the graph, the algorithm finds the shortest path between that node and every other.

Here is the python implementation of Dijkstra algorithm
from heapq import heappush, heappop

# 0 index base dijkstra algorithm
def Dijkstra(graph, source):
    A = [None] * len(graph)
    queue = [(0, source)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: # v is unvisited
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))

    # set -1 for unreachable           
    return [-1 if x is None else x for x in A] 

graph = {
  0: { 1:2, 2:4, 3:1 },
  1: { 2:1, 3:3 },
  2: { 4: 7},
  3: { 2: 2 },
  4: { 0:2, 3:3 }, 
  5: {}
}
source = 0

print Dijkstra(graph, source)

Output:
[0, 2, 3, 1, 10, -1]

1 comments:

Samia Akter said...
This comment has been removed by a blog administrator.

Post a Comment