2023年7月30日发(作者：)

所有节点对之间的最短路问题（AllPairShortestPath）--《算法导论》Floyd这是⼀个动态规划算法。设是之间所有中间节点全部取⾃$<1,2,...,i,...,k>$的⼀条最短路的权重。则状态转移⽅程如下伪代码to

to

to

c++代码void floyd(int n){ memcpy(d,w,sizeof(w));//初始化d(0) for(int k=1 ; k<=n ; ++k) for(int i= 1 ; i<=n ; ++i) for(int j=1 ; j<=n ; ++j) d[i][j] = min(d[i][j],d[i][k]+d[k][j]);}Johnson（⽤于稀疏图）Johnson算法的核⼼思想是直接对每个顶点做⼀次Dijkstra，这样时间复杂度只有（⽤斐波那契堆实现只需）对于稀疏图来说是会渐进优于Floyd算法的，但是我们知道Dijkstra算法只能⽤于权重为正数的情况。所以要对图上的权重进⾏重新映射⼀次。重塑权重值

设为从到的⼀条最短路，则重塑的权重必须满⾜两个条件：1、

2、不包含负环不包含负环下⾯证明取权重映射时满⾜条件。第⼀条肯定满⾜了，因为是预处理出来的常数，第⼆条，当为⼀负权重的环路时，,所以也是负环。构造函数我们采取的⽅法是这样的，添加⼀新节点编号为0，到每⼀个顶点的距离为0，然后我们令,由三⾓不等式,所以简单写⼀下伪代码

伪代码computespfa(G’,0)each vertex veach edgeeach vertex vDijkstra(G,v)totoc++代码void spfa(int s){ for(int i=1 ; i<=nv ; ++i)d[s][i] = INF; d[s][s] = 0; memset(inq,false,sizeof(inq)); queue q; (s); inq[s] = true; while(!()) { int u =(); (); inq[u] = false; for(int i=first[u] ; i!=-1 ; i = nt[i]) { Edge &e = edges[i]; if(d[s][]>d[s][u]+) { d[s][]=d[s][u]+; if(!inq[]){ ();inq[] = true; } } } }}void dijkstra(int s){ bool vis[MAX_V]; memset(vis,false,sizeof(vis));

for(int i=1 ; i<=nv ; ++i)d[s][i] = INF; d[s][s] = 0; priority_queue,greater > q; (pii(0,s)); while(!()) { int u = ().second;(); if(vis[u])continue; else vis[u] = true; for( int i=first[u] ; i!=-1 ; i = nt[i]) { Edge& e = edges[i]; if(d[s][]>d[s][u]+) { (pii(d[s][],)); d[s][] = d[s][u]+ ; } } }}void compute_Go(int last_edge)//最后⼀条边编号{{ int id = last_edge+1; for(int i=1 ; i<=nv ;++i ) { read_edge(0,i,0,id);//向边集数组添加新边 id++; }}void johnson(){ int h[MAX_V]; compute_Go(ne); spfa(0); for(int i=1 ; i<=nv ;++i)h[i] = d[0][i]; //重塑边权重 for(int i=1 ; i<=ne ;++i) { Edge &e = edges[i]; = +h[]-h[]; } for(int i=1 ; i<=nv ; ++i) { dijkstra(i); } //映射回原来的最短路径 for(int i=1 ;i<=nv ;++i) { for(int j=1 ; j<=nv ; ++j) d[i][j] = d[i][j]+h[j]-h[i]; }}Johnson算法实现太复杂，在V不是很⼤的时候都建议⽤floyd。

代码测试题。。。。就是water problem了。。。