rt ，我有一个不太成熟的想法：

对于负权图，遍历每条边，求出最小负边权（记为 $v$ ），然后将所有边权都加上 $|v|$ ，将所有负边权都补为非负边权，然后就可以愉快地用Dijkstra了。

当然，这样求出来的最短路会长很多。去掉的方法：做 Dijkstra 时，记录源点到每个点经过的边数（记为 $toteg$ ），则可如下进行转移：

//x:本次最短路的目标点
for(int i=head[i];i;i=edge[i].next){
    int &y=edge[i].to,&z=edge[i].val;
    if(dist[x]+z<dist[y]){
        dist[y]=dist[x]+z;
        toteg[y]=toteg[x]+1;
    }
}

做完 Dijkstra 之后，记要求最短路的目标点为 $e$ ，则 $dist\,[e\,] - toteg\,[e\,] * |v|$ 为所求。

至于为什么要这么做嘛……

关于 SPFA ，它死了。