Find the shortest path with the least number of edges

Question

I need to modify Dijkstra's algorithm so that if there are several shortest paths I need to find the one with minimum number of edges on the path.

I've been stuck on how to use Dijkstra's method to find multiple shortest paths, how do you do that? doesn't it always output only 1 shortest path? pseudo code or any general direction would be very helpful.

Problem

Answer 1

Instead of assigning every node with the distance from source you can assign the number of edges traversed so far also. So each node will have (distance,edges) instead of distance only. Everything else works as usual and for every terminal node you record the one with minimum value of (distance,edges).

Outcross

ok, and so then when moving forward to the next unchecked node i would compare the edge numbers if the distances were the same... kind of getting this. – Metamorphose

yes, some languages also provide tuple comparison oob. in python you simply have to do (1,2)<(1,1) in c++ you have to use pair<int,int>. – Outcross

Answer 2

Maintain minPathLen field for each vertex for dijktra.

And in loop where you compare

   if(distance(s,u)+edge(u,v)<distance(s,v)) {

         distance(s,v) = distance(s,u) + edge(u,v)
         parent(v) = u
         // Add this statement
         minPathLen(v) = minPathLen(u) + 1
   }

Add another statement:-

 if((distance(s,u)+egde(u,v)==distance(s,v))&&(minPathLen(u)+1<minPathLen(v))) {

       parent(v) = u
       minPathLen(v) = minPathLen(u) + 1     

   }

Ectype

Answer 3

Another option would be to add some small number ε to the weight of every edge, where ε << edgeWeights (for integer edge-weights you can choose ε < gcd(edgeWeights)/numberOfEdges)

The advantage of this approach is that you don't need to write your own pathfinder, you can just use any off-the-shelf implementation.

Turkey

Incorrect . We need to be careful about choosing such small value, as let's say there was a path that had a higher cost previously, but a lesser number of edges, then after this value modification a previously shorter path can end up having a higher value as the number of ε added to it is higher . – Ryun

@sapy: The idea is correct but I had the criteria wrong. It should be fixed now. – Turkey

My solution below is a bit simpler – Ryun

Answer 4

We can add a very small value (let say ε) to each edge . Now the path that will have a higher number of edges will have a higher cost than the path that have lesser number of edges whereas both path had equal minimum path length.

But we need to be careful about choosing such small value, as let's say there was a path that had a higher cost previously, but a lesser number of edges, then after this value modification a previously shorter path can end up having a higher value as the number of ε added to it is higher .

To solve this problem we take the difference between 2 smallest edges . and divide that value by the number of edges to get ε.

Proof - Let's say the graph has n edges. And it’s the shortest path contains (n-1) edges which is slightly high (this value will at least be the difference between 2 minimum edge ) than another path having just 1 edge. So after adding ε to all the edges, the minimum path is still minimum as at least (n+1) epsilon to make it longer than the other path, but it just has (n-1) ε. After value modification apply Dijkstra's algo to find the shortest path between s and t.

Complexity = Complexitytomodifyvalue+ComplexityofDijkstra's = O(E+ E lg V ) = O(E lg V )

Here is the python code -

from heapq import heappop, heappush
from collections import defaultdict


def createAdjacencyList(Graph,epsilon=0):
    AdjacencyList = defaultdict(list)
    for Node1, Node2, edgeCost in Graph:
        AdjacencyList[Node1].append((edgeCost + epsilon, Node2))
    return AdjacencyList


def bestShortestPath(epsilon, s, t, Graph):
    processingQ, visited = [(0, s, "")], set()
    while processingQ:
        # Always return the list item with min cost.
        (totalCost,thisVertices,path) = heappop(processingQ)
        if thisVertices not in visited:
            visited.add(thisVertices)
            path = path + thisVertices
            if thisVertices == t:
                return totalCost - ((len(path) - 1) * epsilon), path

            for thisCost, connectedVertices in Graph.get(thisVertices, ()):
                if connectedVertices not in visited:
                    # It's a python inbuilt Heap. Whenever we will do POP , we will get the element with MinCost .
                    heappush(processingQ, (totalCost+thisCost, connectedVertices, path))

    return float("inf")

if __name__ == "__main__":
    Graph = [ ("A", "B", 3), ("B", "C", 7), ("C", "D", 8),("D", "E", 2), ("E", "F", 3),
              ("A", "G", 7), ("B", "G", 6), ("A", "K", 7), ("C", "I",3), ("F", "K", 9),
              ("G", "H", 4), ("H", "I", 2), ("K", "J", 1), ("G", "L",4), ("I", "M", 3),
              ("I", "O", 3), ("J", "N", 7), ("L", "M", 6), ("M", "N", 7), ("L", "O", 6),
              ("M", "O", 1), ("N", "O", 1), ("L", "H", 1), ("M", "E", 3), ("O", "A", 2),
              ("O", "B", 1), ("O", "C", 1), ("O", "D", 1), ("O", "E", 1), ("K", "N", 8),
    ]
    #  value of epsilon is minimumEdgeWeight/totalNumberOfEdges added to each edge
    minEdge = min(Graph, key=lambda t: t[2])[2]
    secondMinEdge = min(Graph, key=lambda t: [t[2], float("inf")][t[2] == minEdge])[2]
    epsilon = (secondMinEdge - minEdge)/ len(Graph)
    print(createAdjacencyList(Graph).items())
    Graph = createAdjacencyList(Graph, epsilon)
    # (16.0, 'AKNO')  . Though multiple path exists with value 16.0 like ABCIO,AKJNO
    print("Cost and Path from A -> O: is ", bestShortestPath(epsilon, "A", "O", Graph))

Ryun

Answer 5

inspired by BlueRaja

public void updateAdjacencyMatrix()
{
        epsilon = 0.001
        for (int i = 0; i < size; i++)
        {
            for (int j = 0; j < size; j++)
            {
            if (adjacencyMatrix[i, j] != 0)
                adjacencyMatrix[i, j] = adjacencyMatrix[i, j] + epsilon;
        }
    }
}

then call updateAdjacencyMatrix() in your normal Dijkstra's implementation

Aerophone

This wont work if the edge values are lets say 0.0003, .0004 etc.. Epsilon value cant be static . minimumEdgeWeight/totalNumberOfEdges – Ryun

To solve this problem we take the difference between 2 smallest edges . and divide that value by the number of edges to get ε. – Ryun