CODEWITHSUNDEEP
algorithmperformancequeuedijkstrabreadth-first-search
Raoul Duke
Raoul Duke

Reputation: 127

Time complexity of shortest path algorithm

So I wrote an algorithm that finds the number of distinct shortest paths in an undirected, unweighted graph. I believe it is correct and I'm having trouble figuring out what the running time is. All help is greatly appreciated! 

shortestPaths(undirected graph G, startNode v, endNode end)
    initialize  all levels of nodes to -1
    count = 1;
    initialize queue Q = {v}
    level(v) = 0

    while Q is not empty
        curr = pop(Q)

        if( curr == end)
            w = pop(Q)
            while(level(w)==level(curr))
                if(w == end)
                    count++
                w=pop(Q)
            return count

        for all neighbors (nxt) of node curr do 
            if( level(nxt) == -1 )
                level(nxt) = level(curr) + 1
                Push(Q, nxt)
            else if( level(nxt) == level(curr) + 1 )
                Push(Q, nxt)
            else if( level(nxt) > level(curr) + 1)
                Level(nxt) = Level(curr) + 1
    return count

Upvotes: 1

Views: 1902

Answers (1)

Yola
Yola

Reputation: 19041

Run time of your algorithm is exponential. You can avoid this by not pushing a vertex into heap several times, but instead by associating a counter with every vertex and incrementing it with every new path to this vertex.

Try something like this:

initialize  all counts of nodes to 0                     // added
counts(v) = 1                                            // added
...
while Q is not empty
    curr = pop(Q)

    if( curr == end)
        return counts(curr)

    for all neighbors (nxt) of node curr do 
        if( level(nxt) == -1 )
            level(nxt) = level(curr) + 1
            counts(nxt) = counts(curr)                   // added
            Push(Q, nxt)
        else if( level(nxt) == level(curr) + 1 )
            counts(nxt) += counts(curr)                  // added & removed
return 0

And this has the same complexity as BFS - O(|E|+|V|).

Upvotes: 1

Related Questions