如果图具有负边值，那么Dijkstra算法是行不通的。问题在于，一旦一个顶点u被声明是已知的，那么就可能从某个另外的未知顶点v一条回到u的负的路径。在这种情形下，选取从s到v再回到u的路径要比从s到u但不过v更好。

把赋权的和无权的算法结合起来将会解决这个问题，但是要付出运行时间激烈增长的代价。

开始，我们把s放到队列中。

然后，在每一阶段我们当一个顶点v出队。找出所有与v邻接的顶点w，使得dw > dv + Cv,w。

然后更新dw和pw，并在w不在队列中的时候把它放到队列中。可以为每个顶点设置一个比特位（bit)以表示它在队列中的情况。重复这个过程，知道队列为空。

伪代码如下：

void WrightedNegative(Table T){    Queue Q;    Vertex v, W;    Q = CreateQueue(NumVertex);MakeEmpty(Q);    Enqueue(S, Q);    while(!IsEmpty(Q)){        V = Dequeue(Q);        for each W adjacent to V            if(T[V].Dist + Cvw < T[W].Dist){                T[W].Dist = T[V].Dist + Cvw;                T[W].Path = V;                if(W is not already in Q){                    Enqueue(W, Q);                }             }    }    DisposeQueue(Q);}

这里需要注意的是这个算法不适用负值圈。

如果有负值圈存在，那么我们需要记录每个顶点的出队次数，通过任以顶点已经出队NumVertex次，通过任一顶点已经出队NumVertex + 1次后停止运行，否则算法将无线循环下次。