CODEWITHSUNDEEP
c++data-structures
scott
scott

Reputation: 41

How to write a recursive function to calculate shortest path in a graph data structure

Single source shortest path. Given a specified vertex, calculate the shortest path to it for all other nodes. I know there is Dijkstra and Floyd algorithms. But i'm thinking if there is a recursive way to solve it. Here is my work below

int RecursiveShortestPath(int s,int t)
{
    int length;
    int tmp;
    for (Edge e = G.FirstEdge(s); G.isEdge(s); e = G.NextEdge(e))
    {
        if (ToVertex(e) = t)
        {
            length = G.Weight(e);
            return length;
        }
        else if ((tmp = RecursiveShortestPath(ToVertex(e), t)) > 0)
        {
            length = length + tmp;
            return length;
        }
    }
}

I want to calculate the shortest way between two indexed vertices. I'm thinking of doing this by doing recursions and setting a temp value, each time one path is detected i can calculate the length and overwrite the temp value if it's shorter than current. Problem is when returned to the upper layer, it can have several returns for one function call(it may have various sub branch route) thus the outer layer can't tell which is which and it ends up with a mess.

Upvotes: 2

Views: 2131

Answers (1)

user2393256
user2393256

Reputation: 1150

If you do real work I strongly recommend you to not reinvent the wheel and use the Breadth First Search from the boost library.

If this is a school project and you need to implement a recursive algorithm you could go for the Floyd-Warshall algorithm. There is even some pseudo code which you can quite easily convert to c++ code.

Upvotes: 1

Related Questions