Sunday, February 25, 2018

Dijkstra in python

--- code

from collections import defaultdict
from heapq import *
import sys
import time
import os

def dijkstra(edges, f, t):
    g = defaultdict(list)
    for l,r,c in edges:
        g[l].append((c,r))

    q, seen = [(0,f,())], set()
    while q:
        (cost,v1,path) = heappop(q)
        if v1 not in seen:
            seen.add(v1)
            path = (v1, path)
            if v1 == t: return (cost, path)

            for c, v2 in g.get(v1, ()):
                if v2 not in seen:
                    heappush(q, (cost+c, v2, path))

    return float("inf")

if __name__ == "__main__":
  nfrom = sys.argv[1]
  nto = sys.argv[2]
  with open("diagram") as f:
    fr = f.read()
    exec(fr)

    print edges
    print nfrom," --> " , nto
    print dijkstra(edges, nfrom, nto)


    with open("diagram.dot", "w") as ff:
      ff.write("digraph G {\n")
      for i in edges:
        wfrom = i[0]
        wto = i[1]
        label = i[2]
        ff.write(wfrom + " -> " + wto + ' [ label="' + str(label) +'" ];\n')
      ff.write("}")
    time.sleep(1)
os.system("xdot  diagram.dot")



--------



1- use we need a diagram file that list all the node and its code to its neighbor
- diagram file as below
edges = [
        ("A", "B", 7),
        ("A", "D", 5),
        ("B", "C", 8),
        ("B", "D", 9),
        ("B", "E", 7),
        ("C", "E", 5),
        ("D", "E", 15),
        ("D", "F", 6),
        ("E", "F", 8),
        ("E", "G", 9),
        ("F", "G", 11)
    ]



- then we can execute like below to calculate the shortest path from A to E
$  python dijkstra.py A E

No comments:

Post a Comment