0
\$\begingroup\$

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'))
    def add_edge(self, edge):
        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.visited.add(cur)
        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
            self.visited.add(shortest_node_so_far)
            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.add_edge(e)
    g.calculate_shortest_path(1,2)
    print g.shortest_path
    print g.shortest_path_distance
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

If you apply your algorithm twice, as in

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

it would fail badly.

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.

\$\endgroup\$
3
  • \$\begingroup\$ Thanks vpn, agree with you calling twice will fail, and vote up. What do you mean "made properties of a vertex"? Could you show code? \$\endgroup\$
    – Lin Ma
    Commented Apr 22, 2017 at 4:20
  • \$\begingroup\$ BTW, do you see any bugs in my code besides your above comments? \$\endgroup\$
    – Lin Ma
    Commented Apr 22, 2017 at 4:21
  • \$\begingroup\$ Hi vnp, if you could advise on my above questions, it will be great. \$\endgroup\$
    – Lin Ma
    Commented Apr 25, 2017 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.