# Dijkstra's shortest path with max intermediate nodes limitation

Suppose want to calculate the shortest path from one node to all other nodes, with the restriction of intermediate nodes cannot be more than a given number.

My major idea is, following how Dijkstra's algorithm works, with only the exception that when updating shortest path, if I see shortest path intermediate nodes exceeds the given number, I will skip the update. More details, refer to this line and len(self.shortest_path[shortest_node_so_far]+[n[0]])-1 <= max_path_stop

Here is my implementation, any advice on performance improvements in terms of algorithm time complexity, code bugs or code style are appreciated.

Test case is from wikipedia diagram (https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)

Source code in Python 2.7,

from collections import defaultdict
class Graph:
def __init__(self):
self.connections = defaultdict(list)
self.visited = set()
self.shortest_path = defaultdict(list)
self.shortest_path_distance = defaultdict(lambda : float('inf'))
self.connections[edge[0]].append((edge[1], edge[2]))
self.connections[edge[1]].append((edge[0], edge[2]))
def calculate_shortest_path(self, cur, max_path_stop):
self.shortest_path[cur] = [cur]
self.shortest_path_distance[cur] = 0
for n,d in self.connections[cur]:
self.shortest_path_distance[n] = d
self.shortest_path[n].append(cur)
self.shortest_path[n].append(n)
while (len(self.visited) < len(self.connections.keys())):
shortest_so_far = float('inf')
shortest_node_so_far = None
for n,d in self.shortest_path_distance.items():
if n in self.visited:
continue
if d <= shortest_so_far:
shortest_node_so_far = n
shortest_so_far = d
for n in self.connections[shortest_node_so_far]:
if self.shortest_path_distance[shortest_node_so_far] + n[1] < self.shortest_path_distance[n[0]] \
and len(self.shortest_path[shortest_node_so_far]+[n[0]])-1 <= max_path_stop:
self.shortest_path_distance[n[0]]=self.shortest_path_distance[shortest_node_so_far] + n[1]
self.shortest_path[n[0]]=self.shortest_path[shortest_node_so_far]+[n[0]]
if __name__ == "__main__":
g = Graph()
edges = [(1,2,7),(1,3,9),(1,6,14),(2,3,10),(3,6,2),(5,6,9),(5,4,6),(3,4,11),(2,4,15)]
for e in edges:
g.calculate_shortest_path(1,2)
print g.shortest_path
print g.shortest_path_distance


If you apply your algorithm twice, as in

        g.calculate_shortest_path(1,3)
....
g.calculate_shortest_path(1,2)


The reason is that visited, shortest_path, and shortest_path_distance are not, and cannot be, a property of Graph (especially visited). They are ephemeral properties of a particular traversal.
Questionably shortest_path and shortest_path_distance could be made properties of a vertex to allow for some optimization; I not quite sure it worths effort.