dag_shortest_path.py

INF = float('inf')

def dag_shortest_path(graph, weights, torder, s):                                                                                                                         
  d = {v: INF for v in graph}
  d[s] = 0
  pi = {s: None}
  for u in torder:
    for v in graph[u]:
      d_temp = d[u] + weights[u, v]
      if d_temp < d[v]:
        d[v] = d_temp
        pi[v] = u
  return d, pi


if __name__ == '__main__':
  graph = {'A': ['B', 'C'],
           'B': ['C', 'D'],
           'C': ['D', 'E', 'F'],
           'D': ['E', 'F'],
           'E': ['F'],
           'F': []}
  weights = {('A', 'B'): 5, ('A', 'C'): 2,
             ('B', 'C'): 2, ('B', 'D'): 6,
             ('C', 'D'): 7, ('C', 'E'): 4, ('C', 'F'): 2,
             ('D', 'E'): -1, ('D', 'F'): 1,
             ('E', 'F'): -2}
  torder = ['A', 'B', 'C', 'D', 'E', 'F']
  print(dag_shortest_path(graph, weights, torder, 'B'))