CODEWITHSUNDEEP
algorithmdata-structuresgraphgraph-theory
i8abug
i8abug

Reputation: 1682

Can you use Dijkstra's algorithm if there is a negative weight so long as there are no cycles?

Update: I really botched the original question. My original title was "Why do we first do a topological sort for acyclic weighted digraph shortest path problems?" but my question content was about Dijkstra's algorithm. Hopefully since I've changed the title, the question is updated in such a way that it is useful to someone else. The answer to the updated question title is "yes".

Original question:

Why do I need to do a topological sort first? (see code here) Can't I just use Dijkstra's algorithm shown below and avoid the topological sort altogether (little messy syntax-wise but you get the idea)

MinIndexedPriorityQueue waitingEdges = new MinIndexedPriorityQueue
Graph g //some weighted directed graph
double[] distTo = new double[g.vertexCount]
Edge[] edgeTo = new Edge[g.vertexCount]
int source = //init to some value

void minPathInit()
    init distTo to double.MAX_VALUE
    //init first node
    distTo [source] = 0
    visit(source)
    while waitingEdges.count>0
        int vertex = waitingEdges.dequeue()
        relax(vertex )

void relax(v) //note that visit has been renamed to relax
    for each edge in graph.getEdgesFrom(v)
        int to= edge.to
        if edge.weight + distTo [edge.from]<  distTo [to]
            distTo[to] = edge.weight + distTo [edge.from]
            edgeTo[to] = edge
            if waitingEdges.contains(to)
                waitingEdges.change(to,  distTo[to] )
            else
                waitingEdges.enqueue(to,  distTo[to] )


//after everything is initialized
getPathTo(v)
    if not hasBeenVisited[v]
        return null
    Stack path = new Stack
    while edgeTo[v] != source
        path.push(edgeTo[v])
        v = edgeTo[v].from
    return path

I can understand why Dijkstra's algorithm can't handle negative cycles (because it would get stuck in an infinite loop) but if there are no negative cycles, why does it fail as shown (and require the topological sort first)

Update: Ok, I can see that I've botched up this question so I will try to fix it up a bit with an update. Thanks for taking the time to point the hole's out for me. I mistakenly thought AcyclicSP becomes Dijkstra's algorithm when removing the topological sort which is not the case.

However, my question about Dijkstra's algorithm (using the version shown above) remains. Why can't it be used even if there is a negative weight so long as there are no cycles? There is a java version of Dijkstra's algorithm here. Mine is very similar to this (since this guy's book is where I learned about it) but his example is probably easier to read for some of you.

Upvotes: 2

Views: 4161

Answers (3)

AlexWien
AlexWien

Reputation: 28727

It is not possible to use Dijkstra Algo with negative weights. Hundreds have tried, no one was successfull.

Use Bellman-Ford Algo if you have neg. Weights

Upvotes: 1

Ramzi Khahil
Ramzi Khahil

Reputation: 5052

You don't make any topological sort in the original algorithm. But in the case of an a-cyclic graph, then you can decrees the running time to O(V) (while the original running time is O(|V|*log(|V|)). The reason is that you sort in O(|V|) time, and then you can use that order, and don't need any heap (or priority queue). So the over all time decreases to O(|V|).

Upvotes: 3

Peter Lawrey
Peter Lawrey

Reputation: 533492

Dijkstra's algorithm doesn't appear to require a topological sort. Perhaps doing so avoids a bug you have in your implementation.

Dijkstra's algorithm doesn't support negative path costs, but does handle looping cycles. It does this by stopping when it finds that there is a shorter path to a node. A looping path will not be shorter and there for stop (provided the cost is non-negative)

Upvotes: 2

Related Questions