shortest_path.py

# -*- coding: utf-8 -*-

def find_all_paths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    if not graph.has_key(start):
        return []
    paths = []
    for node in graph[start]:
        if node not in path:
            newpaths = find_all_paths(graph, node, end, path)
            for newpath in newpaths:
                paths.append(newpath)
    return paths


def path_time(all_path, time_spent):
    idx_time = {}
    for path_idx in range(len(all_path)):
        time_sum = 0
        for prev,cur in zip(all_path[path_idx][:-1], all_path[path_idx][1:]):
            prev_idx = prev -1
            cur_idx = cur -1
            time_sum += time_spent[prev_idx][cur_idx]

        idx_time.update( {path_idx : time_sum  }   )
    return idx_time



graph = {1: [2,3,4],
         2: [5,6,7],
         3: [5,6,7],
         4: [5,6,7],
         5: [8,9],
         6: [8,9],
         7: [8,9],
         8: [10],
         9: [10]   }

all_path = find_all_paths(graph,1,10)

time_spent = [[0,2,4,3,0,0,0,0,0,0],
[0,0,0,0,7,4,6,0,0,0],
[0,0,0,0,3,2,4,0,0,0],
[0,0,0,0,4,1,5,0,0,0],
[0,0,0,0,0,0,0,1,3,0],
[0,0,0,0,0,0,0,6,3,0],
[0,0,0,0,0,0,0,3,3,0],
[0,0,0,0,0,0,0,0,0,3],
[0,0,0,0,0,0,0,0,0,4],
[0,0,0,0,0,0,0,0,0,0]]



print path_time(all_path,time_spent)
print all_path[6]
print all_path[12]
print all_path[15]