Can Dijkstra's Single Source Shortest Path Algorithm detect an infinite cycle in a graph?

Question

So I came to this beautiful problem that asks you to write a program that finds whether a negative infinity shortest path exists in a directed graph. (Also can be thought of as finding whether a "negative cycle" exists in the graph). Here's a link for the problem:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=499

I successfully solved the problem by running Bellman Ford Algorithm twice by starting with any source in the graph. The second time I run the algorithm, I check if a node can be relaxed. If so, then there is definitely a negative cycle in the graph. Below is my C++ code:

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
    int test;
    cin>>test;

    for(int T=0; T<test; T++)
    {

        int node, E;

        cin>>node>>E; 

        int **edge= new int *[E];
        for(int i=0; i<E; i++)
        {
            edge[i]= new int [3];
            cin>>edge[i][0]>>edge[i][1]>>edge[i][2];
        }

        int *d= new int [node];

        bool possible=false;

        for(int i=0; i<node;i++)
        {
            d[i]= 999999999;
        }

        d[node-1]=0;

        for(int i=0; i<node-1; i++)
        {

            for(int j=0; j<E; j++)
            {
                if(d[edge[j][1]]>d[edge[j][0]]+edge[j][2])
                    d[edge[j][1]]=d[edge[j][0]]+edge[j][2];
            }
        }

        // time to judge!
        for(int i=0; i<node-1; i++)
        {

            for(int j=0; j<E; j++)
            {
                if(d[edge[j][1]]>d[edge[j][0]]+edge[j][2])
                {
                    possible=true;
                    break;
                }

            } 

            if(possible)
                break;

        }

        if(possible)
            cout<<"possible"<<endl;
        else
            cout<<"not possible"<<endl;

    }
}

A professor told me once that Dijkstra's shortest path algorithm cannot find such negative cycle, but he did not justify it. I actually doubt this claim.

My question is, can Dijktstra's single source shortest path algorithm detect that negative cycle?

Of course, I can try Dijkstra's and check whether it will work, but I was excited to share this idea with you.

Solution 1

You misunderstood your professor: he must have said that Dijkstra's algorithm will not work if there is a negative cycle in the graph. Positive cycles are allowed.

The reason the algorithm will not work on graphs with negative cycles is that the shortest path in such graphs is undefined: once you get to a negative cycle, you can bring the cost of your "shortest path" as low as you wish by following the negative cycle multiple times.

Consider the example above: you start at the vertex Start, and arrive at A with the cost of 1. Then you go to B with the total cost of -1, to C with the total of -4, and now you can go back to A with the total cost of zero. By extending the sequence Start-A-B-C-A-B-C-A-B-C-...-Finish you could reduce the cost of a path from Start to Finish to as small a negative number as you wish.

Note that the negative cycle restriction applies to all algorithms for finding shortest path in a graph. The restriction on Dijkstra's algorithm is even stronger: it prohibits all negative edges.

It is certainly possible to modify Dijkstra's algorithm to detect negative cycles, but there is no point in doing so, because you have a stronger restriction of having no negative edges.

Solution 2

No algorithm neither Dijkstra's nor Bellman-Ford nor Floyd-Warshall work on graphs with negative cycle but the latter two can detect one whereas Dijkstra's cannot because Dijkstra's is greedy whereas others use dynamic programming. Moreover Dijkstra doesn't work with negative weights even without negative cycles.

Comments

[Traveling Salesman]

I agree. This is what he said. But can you justify why Dijkstra's algorithm will not work if there is a negative cycle in the graph?

[Traveling Salesman]

I'll check it. Many Thanks.

[Groo]

@Traveling: once you mark a node as "visited" (or "out", as in this animation), you need to be sure that this really is the lowest possible cost of reaching that node. If there were negative cycles, then there would exist a cycle which would result in a smaller cost for an already processed node.

[V G]

Why does wikipedia says that Dijkstra's algorithm works with non-negative edges (not mentioning negative-cycles)? Do you mean you can convert a graph without negative cycles into one without negative edges at all?

[Sergey Kalinichenko]

@AndreiI You are right, Dijkstra's algorithm will not work if any weight is negative. Shortest paths are undefined in graphs with negative cycles.

[V G]

Than I do not understand why all of you discuss about negative cycles, when the easier problem of negative-weight edge cannot be solved with Dijkstra's (and the counter example would be easier). Anyway, you explained it nice. Besides: how did you generate so quickly the image with the graph?

[smac89]

The above explanation is wrong. When Dijkstra gets to node C, the next node it will choose is Finish. This is because of 2 reasons: Once a node is marked as visited using Dijkstra, it is not visited again; See this answer for an explanation. Next reason is because the distance to C is -3 then the next viable option after visiting C is Finish because -3 + 1 < -3 + 4

[Sergey Kalinichenko]

@Smac89 I rewrote the explanation to say that the negative cycle restriction is generic, and that Dijkstra's algorithm has an additional restriction of disallowing negative edges. Thanks for the comment!