Skip to content

Instantly share code, notes, and snippets.

@zaz
Last active Nov 23, 2020
Embed
What would you like to do?
Dijkstra's algorithm — Python
# Zaz Brown
# github.com/zaz/dijkstra
"""An efficient algorithm to find shortest paths between nodes in a graph."""
from collections import defaultdict
class Digraph(object):
def __init__(self, nodes=[]):
self.nodes = set()
self.neighbours = defaultdict(set)
self.dist = {}
def addNode(self, *nodes):
[self.nodes.add(n) for n in nodes]
def addEdge(self, frm, to, d=1e309):
self.addNode(frm, to)
self.neighbours[frm].add(to)
self.dist[ frm, to ] = d
def dijkstra(self, start, maxD=1e309):
"""Returns a map of nodes to distance from start and a map of nodes to
the neighbouring node that is closest to start."""
# total distance from origin
tdist = defaultdict(lambda: 1e309)
tdist[start] = 0
# neighbour that is nearest to the origin
preceding_node = {}
unvisited = self.nodes
while unvisited:
current = unvisited.intersection(tdist.keys())
if not current: break
min_node = min(current, key=tdist.get)
unvisited.remove(min_node)
for neighbour in self.neighbours[min_node]:
d = tdist[min_node] + self.dist[min_node, neighbour]
if tdist[neighbour] > d and maxD >= d:
tdist[neighbour] = d
preceding_node[neighbour] = min_node
return tdist, preceding_node
def min_path(self, start, end, maxD=1e309):
"""Returns the minimum distance and path from start to end."""
tdist, preceding_node = self.dijkstra(start, maxD)
dist = tdist[end]
backpath = [end]
try:
while end != start:
end = preceding_node[end]
backpath.append(end)
path = list(reversed(backpath))
except KeyError:
path = None
return dist, path
def dist_to(self, *args): return self.min_path(*args)[0]
def path_to(self, *args): return self.min_path(*args)[1]
@christopher-abastar

This comment has been minimized.

Copy link

@christopher-abastar christopher-abastar commented Feb 2, 2017

Hi,

i have these sample datasets. Seems to be not working from F to E.

def main():
    graph = Digraph(nodes = ['A','B','C','D','E','F','G'])
    graph.add_edge("A", "B", 7)
    graph.add_edge("A", "D", 5)
    graph.add_edge("B", "C", 8)
    graph.add_edge("B", "D", 9)
    graph.add_edge("B", "E", 7)
    graph.add_edge("C", "E", 5)
    graph.add_edge("D", "E", 15)
    graph.add_edge("D", "F", 6)
    graph.add_edge("E", "F", 8)
    graph.add_edge("E", "G", 9)
    graph.add_edge("F", "G", 11)

    print(graph.min_path("A","D"))
    print(graph.min_path("A","E"))
    print(graph.min_path("F","G"))
    print(graph.min_path("F","E"))
if __name__ == "__main__":
    main()
@PDelerm

This comment has been minimized.

Copy link

@PDelerm PDelerm commented Feb 15, 2017

I got this error :

Estimation du Traffic dans les réseaux optiques multi-débit

Entrez la Source : 1
Entrez la Destination : 14
Traceback (most recent call last):
File "NET.py", line 100, in
print(graph.min_path(source, destination))
NameError: name 'graph' is not defined

@ctriley

This comment has been minimized.

Copy link

@ctriley ctriley commented Jul 10, 2017

I may be doing something wrong, but I believe this code will not work for multiple calls of dijkstra's algorithm. It seems to remove all of the nodes from the graph every time this algorithm is called.

unvisited = self.nodes and then unvisited.remove(min_node).

To fix this I changed line 28 to unvisited = copy.copy(self.nodes)
 

@khairakiran6

This comment has been minimized.

Copy link

@khairakiran6 khairakiran6 commented Sep 6, 2020

Can u help how to take input from a file . like a/ b/ 8 is format from node a to b distance is 8

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment