[Edu-sig] shortest path algorithm based on guido's essay and a post by June Kim

[Christian Jeitler]

hello!

this code shows how to calculate the shortest path between two cities on a map
based on:
http://www.python.org/doc/essays/graphs.html
i have changed the code with the hlp of a news article by June Kim.
For small graphs it works better than the Dijkstra algorithm.

If anybody has an idea how to speed up this algorithm ?

By the way I am looking forward to the second part of the essay.

def weight(path):
     weight_of_path= 0
     for node in path:
         weight_of_path = weight_of_path + node[1]
     return weight_of_path

def find_shortest_path(graph, start, end, path=[]):

     path = path + [start]

     path_hlp=[]
     for node_hlp in path:
         path_hlp = path_hlp + [node_hlp[0]]

     if start[0] == end:
         return path

     shortest_path = None

     for node in graph[start[0]]:
         if node[0] not in path_hlp:
             new_path = find_shortest_path(graph, node, end, path)
             if new_path:
               if not shortest_path or weight(new_path) < 
weight(shortest_path):
                     shortest_path = new_path
     return shortest_path

# real geographic area in vienna

graph = {'A':[('B',513)],
          'B':[('A',513),('C',1513),('J',1684),('K',1107)],
          'C':[('B',1513),('D',406),('K',654)],
          'D':[('C',406),('E',834),('L',860)],
          'E':[('D',834),('L',889),('F',2472)],
          'F':[('E',2472),('Z',170),('M',765),('G',2796)],
          'G':[('F',2796),('N',1317),('H',737)],
          'H':[('G',737),('P',1181),('I',1072)],
          'I':[('H',1072),('Q',1020),('J',467)],
          'J':[('I',467),('Q',565),('B',1684)],
          'K':[('B',1107),('C',654),('P',1340),('Q',719)],
          'Q':[('K',719),('I',1020),('J',565)],
          'L':[('D',860),('E',889),('M',729),('O',648)],
          'O':[('L',648),('N',709),('P',153)],
          'M':[('L',729),('F',765),('N',444)],
          'N':[('M',444),('G',1317),('O',709)],
          'P':[('O',153),('H',1181),('K',1340)],
          'Z':[('F',170)]}

pathfinder = find_shortest_path(graph,('A',0),'Z')