Search code examples
algorithmgraphshortest-pathdijkstra

Is it possible to determine the hop-count when performing Dijkstra?

Thank the codes from @trincot I can modify the Dijkstra to obtain the shortest path between a given source node and destination node. Moreover, I tried to count the hop when performing the Dijkstra to find the shortest path, when the hop-count exceeds the pre-defined Max_hop, the Dijkstra will be terminated, but I was failed.

Hop is defined as the (N - 1), where N is the number of vertices contained in the shortest paths.

Absolutely, after finding the shortest path, we can easily count the hop number. However, during the Dijkstra's path searching, can we count the hop between a given source and?

from heapq import heappop, heappush
def dijkstra(adjList, source, sink):
    n = len(adjList)   
    parent = [None]*n  
    heap = [(0,source,0)]
    explored_node=[]
    hop_count = 0
    Max_hop = 8    
    while heap:
        distance, current, came_from = heappop(heap)
        if parent[current] is not None:  # skip if already visited
            continue
        parent[current] = came_from  # this also marks the node as visited
        if sink and current == sink:  # only correct place to have terminating condition
            # build path
            path = [current]

            while current != source:
                current = parent[current]
                path.append(current)
            path.reverse()
            hop_count -=1
            print("Hop count is ",hop_count)
            
            return 1, distance, path
        for (neighbor, cost) in adjList[current]:
            if parent[neighbor] is None:  # not yet visited
                heappush(heap, (distance + cost, neighbor,  current))
                hop_count = hop_count + 1
                if hop_count > Max_hop:
                    print("Terminate")
adjList =[

[],

[[2,3],[4,11],[5,5]],
[[1,3],[3,5],[5,11],[6,7]],
[[2,5],[6,3]],
[[1,11],[5,15],[7,9]],
[[1,5],[2,11],[6,3],[7,6],[8,3],[9,9]],
[[2,7],[3,3],[5,3],[9,10]],
[[4,9],[5,6],[8,1],[10,11],[11,8]],
[[5,3],[7,1],[9,9],[11,11]],
[[5,9],[6,10],[8,9],[11,3],[12,8]],
[[7,11],[13,7],[14,3]],
[[7,8],[8,11],[9,3],[12,8],[14,6]],
[[9,8],[11,8],[15,11]],
[[10,7],[15,3]],
[[10,3],[11,6],[15,9]],
[[12,11],[13,3],[14,9]],
]

flag, dist, path = dijkstra(adjList,1,15)

print("found shortest path {}, which has a distance of {}".format(path, dist))

The graph of adjList is as shown: (the red line is the shortest path from 1 to 15) enter image description here

I know this is incorrect since when Dijkstra iterates the neighbor, I make hop_cout + 1 that represents the number of explored nodes rather than the hop_count.

In my opinion, there are two significant issues that need to be addressed.

  1. When the shortest distance between a parent_node and a neighbor_node is determined, the hop_count can be added 1. But, Dijkstra finds the shortest path by iterating the neighbor nodes, and the array that stores the shortest distance is updated gradually during path searching. How to determine Dijkstra has already found the shortest distance between a parent_node and a neighbor_node?
  2. Only condition 1 is not enough, even we can know when Dijkstra has found the shortest distance between two nodes, but how do we know whether the neighbor_node will be included in the shortest path between a given source and destination?

In summary, if we want to know the current hop-count during Dijkstra is running, we need to set hop_count +1, When the shortest path from the parent_node to the neighbor_node has been determined, and the neighbor_node will be included to the shortest path from the source to the destination node.

To better define the problem, as shown in this figure, the red line is the shortest path between node 1 and node 15, the shortest path is 1 ->5 ->8 ->7 ->10 ->13 ->15.

  1. When node 2 is explored and the shortest distance between node 1 and node 2 is determined as 3, the hop_count cannot be added 1 since node 2 is not contained in the shortest path between 1 and 15.
  2. When node 5 is explored and the shortest distance between node 1 and node 5 is determined as 5, the hop_count should be added 1 since node 5 is contained in the shortest path between 1 and 15.

Is my understanding correct? May I hear your idea that "Is it possible to determine the hop-count when performing Dijkstra? "

Solution

  • As the heap will have nodes that represent paths having varying lengths, you cannot hope to use one variable for the hop count. You would need to add the hop count as an additional information in the tuples that you put on the heap, as it is specific to each individual path.

    Secondly, you would need to allow that different paths to the same node are allowed to be extended further, as some of these might drop out because of the hop limit, while another may stay under that limit. So concretely, when a more costly path is found to an already visited node, but the number of hops is less, it should still be considered. This means that came_from is not a good structure now (as it only allows one path to pass via a node). Instead we can use a linked list (of back-references) that is included in the heap-element.

    NB: I would also make max_hop a parameter to the function:

    from heapq import heappop, heappush

def dijkstra(adjList, source, sink, max_hop=8):  # make max_hop a parameter
    n = len(adjList)   
    least_hops = [n]*n  # Used for deciding whether to visit node via different path
    heap = [(0, 0, (source, None))]  # came_from is now a linked list: (a, (b, (c, None)))
    while heap:
        distance, hop_count, chain = heappop(heap)  # hop_count is part of tuple
        current = chain[0]
        if hop_count >= least_hops[current]:
            continue  # Cannot be an improvement
        least_hops[current] = hop_count
        if sink and current == sink:
            print("Hop count is ", hop_count)
            path = []
            while chain:
                current, chain = chain  # Unwind linked list
                path.append(current)
            return 1, distance, path[::-1]
        
        if hop_count >= max_hop:  # no recursion beyond max_hop
            print("Terminate")
            continue
        hop_count += 1  # Adjusted for next pushes unto heap
        for neighbor, cost in adjList[current]:
            heappush(heap, (distance + cost, hop_count, (neighbor, chain)))  # Prepend neighbor

    As to your other question:

    How to determine Dijkstra has already found the shortest distance between a parent_node and a neighbor_node?

    We don't determine this immediately and allow multiple paths to the same node to co-exist. The if in the for loop detects whether the node was already visited and the number of hops to it is not an improvement: this means it had received priority on the heap and had been pulled from it in an earlier iteration of the main while loop, and thus we already have a shortest path to that node. This if prevents us from pushing a useless "alternative" path on the heap: even if the shortest path needs to be rejected later because it cannot stay within the hop limit, an alternative that did not use fewer hops, cannot hope to then stay within the limit either, so it can be rejected now.