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\$
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
    Apr 22 '17 at 4:20
  • \$\begingroup\$ BTW, do you see any bugs in my code besides your above comments? \$\endgroup\$
    – Lin Ma
    Apr 22 '17 at 4:21
  • \$\begingroup\$ Hi vnp, if you could advise on my above questions, it will be great. \$\endgroup\$
    – Lin Ma
    Apr 25 '17 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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