Dijkstra's algorithm — Python. Deprecated: Find the updated version at https://github.com/zaz/dijkstra

dijkstra.py

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

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

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

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)
 

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

@christopher-abastar @PDelerm @ctriley @khairakiran6 Sorry for not being responsive on this.

The most up-to-date version is at zaz/dijkstra. Please create an issue there if there are still bugs.