Can Dijkstra's Single Source Shortest Path Alg

问题:

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.

回答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.

回答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.