最短路径算法——Dijkstra,Bellman-Ford,Floyd-Warshall,Johnson

DSQiu

浏览: 1407993 次
性别:
来自: 广州

最近访客更多访客>>

ymgjava

spike_wq

sdsunrunner

hackxboy

博主相关

博客

微博

相册

留言

关于我

博客专栏

: NGUI所见即所得
浏览量：196477

: Effective C# ...
浏览量：0

文章分类

社区版块

存档分类

博客分类：

学习笔记
转载整理
图算法

Dijkstra Bellman-Ford Floyd-Warshall Johnson

最短路径算法——Dijkstra,Bellman-Ford,Floyd-Warshall,Johnson，无一幸免

本文内容框架：

§1 Dijkstra算法

§2 Bellman-Ford算法

§3 Floyd-Warshall算法

§4 Johnson算算法

§5 问题归约

§6 小结

常用的最短路径算法有：Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法

最短路径算法可以分为单源点最短路径和全源最短路径。

单源点最短路径有Dijkstra算法和Bellman-Ford算法，其中Dijkstra算法主要解决所有边的权为非负的单源点最短路径，Bellman-Ford算法可以适用权值有负值的问题。

全源最短路径主要有Floyd-Warshall算法和Johnson算法，其中Floyd算法可以检测图中的负环并可以解决不包括负环的图中全源最短路径问题，Johnson算法相比Floyd-Warshall算法，效率更高。

算法性能分析

在分别讲解这四个算法之前先来理清下这个四个算法的复杂度：Dijkstra算法直接实现时间复杂度是O(n²),空间复杂度是O(n)(保存距离和路径)，二叉堆实现时间复杂度变成O((V+E)logV)，Fibonacci Heap可以将复杂度降到O(E+VlogV)；Bellman-Ford算法时间复杂度是O(V*E)，SPFA是时间复杂度是O(kE)；Floyd-Warshall算法时间复杂度是O(n³)，空间复杂度是O(n²)；Johnson算法时间复杂度是O( V * E * lgd(V) )，比Floyd-Warshall算法效率高。

最短路径算法之Dijkstra算法

╔

§1 Dijkstra算法

Dijkstra算法思想

Dijkstra算法思想为：设G=(V,E)是一个带权有向图（无向可以转化为双向有向），把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

Dijkstra算法具体步骤　　

（1）初始时，S只包含源点，即S＝{v}，v的距离dist[v]为0。U包含除v外的其他顶点，U中顶点u距离dis[u]为边上的权值（若v与u有边））或∞（若u不是v的出边邻接点即没有边<v,u>）。

（2）从U中选取一个距离v(dist[k])最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。

（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（u∈ U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权(即如果dist[k]+w[k,u]<dist[u]，那么把dist[u]更新成更短的距离dist[k]+w[k,u])。

（4）重复步骤（2）和（3）直到所有顶点都包含在S中(要循环n-1次)。

╝①

Dijkstra算法实现

╔

直接实现

最简单的实现方法就是，在每次循环中，再用一个循环找距离最短的点，然后用任意的方法更新与其相邻的边，时间复杂度显然为O(n²)

对于空间复杂度：如果只要求出距离，只要n的附加空间保存距离就可以了（距离小于当前距离的是已访问的节点，对于距离相等的情况可以比较编号或是特殊处理一下）。如果要求出路径则需要另外V的空间保存前一个节点，总共需要2n的空间。

╝②

╔

/*********************************
*   最短路径---Dijkstra算法实现 
*   　　　HDU：2544 
*   BLOG:www.cnblogs.com/newwy
*   AUTHOR:Wang Yong
**********************************/
#include <iostream>
#define MAX 100
#define INF 1000000000
using namespace std;
 int dijkstra (int mat[][MAX],int n, int s,int f)
 {
     int dis[MAX];
     int mark[MAX];//记录被选中的结点 
     int i,j,k = 0;
     for(i = 0 ; i < n ; i++)//初始化所有结点，每个结点都没有被选中 
         mark[i] = 0;
    for(i = 0 ; i < n ; i++)//将每个结点到start结点weight记录为当前distance 
    {
        dis[i] = mat[s][i];
        //path[i] = s;
    }
    mark[s] = 1;//start结点被选中 
    //path[s] = 0;
    dis[s] = 0;//将start结点的的距离设置为0 
    int min ;//设置最短的距离。 
    for(i = 1 ; i < n; i++)
    {
        min = INF;
        for(j = 0 ; j < n;j++)
        {
            if(mark[j] == 0  && dis[j] < min)//未被选中的结点中，距离最短的被选中 
            {
                min = dis[j] ;
                k = j;
            }
        }
        mark[k] = 1;//标记为被选中 
        for(j = 0 ; j < n ; j++)
        {
            if( mark[j] == 0  && (dis[j] > (dis[k] + mat[k][j])))//修改剩余结点的最短距离 
            {
                dis[j] = dis[k] + mat[k][j];
            }
        }
    }
    return dis[f];    
 } 
 int mat[MAX][MAX];
int main()
{
    int n,m;
    while(scanf("%d %d",&n,&m))
    {
        int a,b,dis;
        if(n == 0 || m == 0)
            break;
        int i,j;
        for(i = 0 ; i < n;i++)
            for(j = 0 ; j < n; j++)
                mat[i][j] = INF;
        for(i = 0 ; i < m ;i++)
        {
            scanf("%d %d %d",&a,&b,&dis);
            --a,--b;
            if(dis < mat[a][b] || dis < mat[b][a])
            mat[a][b] = mat[b][a] = dis;
        }
        int ans = dijkstra(mat,n,0,n-1);
        printf("%d\n",ans);
    }
 
}

╝⑤

╔

二叉堆实现

使用二叉堆(Binary Heap)来保存没有扩展过的点的距离并维护其最小值，并在访问每条边的时候更新，可以把时间复杂度变成O((V+E)logV)。

当边数远小于点数的平方时，这种算法相对来说有很好的效果。但是当E=O(V2)时（有时候表现为不限制边的条数），用二叉堆的优化反倒会更慢。因为此时的复杂度是O(V+V*2logV)，小于不用堆的实现的O(n²)的复杂度。

另外此时要用邻接表保存边，使得扩展边的总复杂度为O(E)，否则复杂度不会减小。

空间复杂度：这种算法需要一个二叉堆，及其反向指针，另外还要保存距离，所以所用空间为3V。如果保存路径则为4V。

具体思路：先将所有的点插入堆，并将值赋为极大值(maxint/maxlongint)，将原点赋值为0，通过松弛技术（relax）进行更新以及设定为扩展。

╝②

╔

int  GraphDijk(struct Graph *g, int root, int *parent, int *distance)
{
	// 将除根结点之外的点都放入堆中，设置所有键为INFINITY
	// 遍历根结点发出的边，将其最短路径设为相应权值，并维持堆性质
	// RemoveTop，此结点已经取最短路径，如果为INFINITY，则终止算法
	// 否则，将其状态设为已标记，并设为根结点
	// loop back
	parent[root] = root;
	int reflection[g->V];
	int heap_real[g->V - 1];
	for (int i=0,j=0; i < g->V; i++) {
		if (i == root) {
			distance[i] = 0;
		} else {
			distance[i] = INFINITY;
			heap_real[j++] = i;
			reflection[i] = j;
		}
	}
 
	struct Edge *e;
	struct list_t *iter;
	int *heap = heap_real - 1;
	int base = 0;  /* euqal to distance[root]  */
	int size = g->V - 1;
	int length;
	do {
		iter = list_next(&(g->vertices + root)->link);
		for (; iter; iter = list_next(iter)) {
			e = list_entry(iter, struct Edge, link);
			length = base + e->weight;
			if (length < distance[e->to]) { 
				HeapDecreaseKey(heap, size, 
					distance, reflection, 
					reflection[e->to], length);
				parent[e->to] = root;
			}
		}
		root = HeapRemoveTop(heap, size, distance, reflection);
		base = distance[root];
 
		if (distance[root] == INFINITY) { 
			/* remain nodes in heap  is not accessible */
			return g->V - (size + 1); /* 返回强连通分支结点数 */	
		}
	} while (size);
 
	/* successfull end algorightm  */
	return g->V; 
}

╝④

再献上一个实现

╔

    /*很裸很水的最短路，练习二叉堆优化的Dijstra～

    之前二叉堆优化的Prim敲了好几遍前后花了不下八个小时调试还是没有调试成功，
    但是还好，熟悉了优先队列的操作。

    十几天后的今天重新想起这个，终于调出来了堆优化的Dijstra。理解之后还是蛮简单的。

    一些写法并不是最优的，例如heap的实现中可以减少交换元素等。但是有这个自己写的AC
    过的Dijkstra在，以后写二叉堆优化的Prim/Dijkstra和其它优先队列的题目就可以拿它对照着Debug了。

    2011-07-24 23:00
*/


#include <stdio.h>

#define MAXN 1200
#define MAXM 1200000
#define INF 19930317

struct node
{
    int d, v, p;
}heap[MAXN];
int pos[MAXN], hl;

int e[MAXM], cost[MAXM], next[MAXM], g[MAXN], size;

int m, n, s, t;

void insert(int u, int v, int w)
{
    e[++size] = v;
    next[size] = g[u];
    cost[size] = w;
    g[u] = size;
}


void swap(int a, int b)
{
    heap[0] = heap[a];
    heap[a] = heap[b];
    heap[b] = heap[0];
    pos[heap[a].v] = a;
    pos[heap[b].v] = b;
}

void heapfy()
{
    int i = 2;
    while (i <= hl)
    {
        if ((i < hl) && (heap[i + 1].d < heap[i].d))
            i++;
        if (heap[i].d < heap[i >> 1].d)
        {
            swap(i, i >> 1);
            i <<= 1;
        }
        else
            break;
    }
}



void decrease(int i)
{
    while ((i != 1) && (heap[i].d < heap[i >> 1].d))
    {
        swap(i, i >> 1);
        i >>= 1;
    }
}

void relax(int u ,int v, int w)
{
    if (w + heap[pos[u]].d < heap[pos[v]].d)
    {
        heap[pos[v]].p = u;
        heap[pos[v]].d = w + heap[pos[u]].d;
        decrease(pos[v]);
    }
}

void delete_min()
{
    swap(1, hl);
    hl--;
    heapfy();
}

void init()
{
    int u ,v ,w, i;

    scanf("%d%d", &m, &n);
    for (i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &u, &v, &w);
        insert(u, v, w);
        insert(v, u, w);
    }
    s = 1;
    t = n;
}



int dijkstra()
{
    int u, p, i;

    for (i = 1; i <= n; i++)
    {
        heap[i].v = pos[i] = i;
        heap[i].d = INF;
    }
    heap[s].p = s;
    heap[s].d = 0;
    swap(1, s);
    hl = n;
    while (hl)
    {
        u = heap[1].v;
        delete_min();
        p = g[u];
        while (p)
        {
            if (pos[e[p]] <= hl)
                relax(u, e[p], cost[p]);
            p = next[p];
        }

    }
}
int main()
{
    init();
    dijkstra();
    printf("%d\n", heap[pos[t]].d);
    return 0;
}

╝③

╔

菲波那契堆实现

用类似的方法，使用Fibonacci Heap可以将复杂度降到O(E+VlogV)，但实现比较麻烦。因此这里暂不列举。

╝②

最短路径算法之Bellman-Ford算法

§2 Bellman-Ford算法

╔

Bellman-Ford算法思想

Bellman-Ford算法能在更普遍的情况下（存在负权边）解决单源点最短路径问题。对于给定的带权（有向或无向）图 G=（V,E），其源点为s，加权函数 w是边集 E 的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到图G的任意顶点v的最短路径d[v]。

Bellman-Ford算法流程：

（1）初始化：将除源点外的所有顶点的最短距离估计值 d[v] ←+∞, d[s] ←0;

（2）迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离；（运行|v|-1次）

（3）检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在 d[v]中。

算法描述如下：

Bellman-Ford(G,w,s) ：boolean //图G ，边集函数 w ，s为源点

1 for each vertex v ∈ V（G） do //初始化 1阶段

2 d[v] ←+∞

3 d[s] ←0; //1阶段结束

4 for i=1 to |v|-1 do //2阶段开始，双重循环。

5 for each edge（u,v） ∈E(G) do //边集数组要用到，穷举每条边。

6 If d[v]> d[u]+ w(u,v) then //松弛判断

7 d[v]=d[u]+w(u,v) //松弛操作 2阶段结束

8 for each edge（u,v） ∈E(G) do

9 If d[v]> d[u]+ w(u,v) then

10 Exit false

11 Exit true

下面给出描述性证明：

首先指出，图的任意一条最短路径既不能包含负权回路，也不会包含正权回路，因此它最多包含|v|-1条边。

其次，从源点s可达的所有顶点如果存在最短路径，则这些最短路径构成一个以s为根的最短路径树。Bellman-Ford算法的迭代松弛操作，实际上就是按顶点距离s的层次，逐层生成这棵最短路径树的过程。

在对每条边进行1遍松弛的时候，生成了从s出发，层次至多为1的那些树枝。也就是说，找到了与s至多有1条边相联的那些顶点的最短路径；对每条边进行第2遍松弛的时候，生成了第2层次的树枝，就是说找到了经过2条边相连的那些顶点的最短路径……。因为最短路径最多只包含|v|-1 条边，所以，只需要循环|v|-1 次。

每实施一次松弛操作，最短路径树上就会有一层顶点达到其最短距离，此后这层顶点的最短距离值就会一直保持不变，不再受后续松弛操作的影响。（但是，每次还要判断松弛，这里浪费了大量的时间，怎么优化？单纯的优化是否可行？）

如果没有负权回路，由于最短路径树的高度最多只能是|v|-1，所以最多经过|v|-1遍松弛操作后，所有从s可达的顶点必将求出最短距离。如果 d[v]仍保持 +∞，则表明从s到v不可达。

如果有负权回路，那么第 |v|-1 遍松弛操作仍然会成功，这时，负权回路上的顶点不会收敛。

╝⑥

Bellman-Ford算法实现

╔

#include<iostream>
#include<cstdio>
using namespace std;

#define MAX 0x3f3f3f3f
#define N 1010
int nodenum, edgenum, original; //点，边，起点
typedef struct Edge //边
{
	int u, v;
	int cost;
}Edge;
Edge edge[N];
int dis[N], pre[N];
bool Bellman_Ford()
{
	for(int i = 1; i <= nodenum; ++i) //初始化
		dis[i] = (i == original ? 0 : MAX);
	for(int i = 1; i <= nodenum - 1; ++i)
		for(int j = 1; j <= edgenum; ++j)
			if(dis[edge[j].v] > dis[edge[j].u] + edge[j].cost) //松弛（顺序一定不能反~）
			{
				dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;
				pre[edge[j].v] = edge[j].u;
			}
			bool flag = 1; //判断是否含有负权回路
			for(int i = 1; i <= edgenum; ++i)
				if(dis[edge[i].v] > dis[edge[i].u] + edge[i].cost)
				{
					flag = 0;
					break;
				}
				return flag;
}

void print_path(int root) //打印最短路的路径（反向）
{
	while(root != pre[root]) //前驱
	{
		printf("%d-->", root);
		root = pre[root];
	}
	if(root == pre[root])
		printf("%d\n", root);
}

int main()
{
	scanf("%d%d%d", &nodenum, &edgenum, &original);
	pre[original] = original;
	for(int i = 1; i <= edgenum; ++i)
	{
		scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].cost);
	}
	if(Bellman_Ford())
		for(int i = 1; i <= nodenum; ++i) //每个点最短路
		{
			printf("%d\n", dis[i]);
			printf("Path:");
			print_path(i);
		}
	else
		printf("have negative circle\n");
	return 0;
}

╝⑦

Bellman-Ford算法优化——SPFA算法

循环的提前跳出：在实际操作中，贝尔曼-福特算法经常会在未达到V-1次前就出解，V-1其实是最大值。于是可以在循环中设置判定，在某次循环不再进行松弛时，直接退出循环，进行负权环判定。

具体做法是用一个队列保存待松弛的点，然后对于每个出队的点依次遍历每个与他有边相邻的点（用邻接表效率较高），如果该点可以松弛并且队列中没有该点则将它加入队列中(只有进行松弛操作的点才会对它的邻接点有影响，也就是说其邻接点才需要松弛操作)，如此迭代直到队列为空。

SPFA算法实现

╔

#include <iostream>
#include <queue>
using namespace std;
const long MAXN=10000;
const long lmax=0x7FFFFFFF;
typedef struct  
{
    long v;
    long next;
    long cost;
}Edge;
Edge e[MAXN];
long p[MAXN];
long Dis[MAXN];
bool vist[MAXN];
queue<long> q;
long m,n;//点,边
void init()
{
    long i;
    long eid=0;
    memset(vist,0,sizeof(vist));
    memset(p,-1,sizeof(p));
    fill(Dis,Dis+MAXN,lmax);
    while (!q.empty())
    {
        q.pop();
    }
    for (i=0;i<n;++i)
    {
        long from,to,cost;
        scanf("%ld %ld %ld",&from,&to,&cost);
        e[eid].next=p[from];
        e[eid].v=to;
        e[eid].cost=cost;
        p[from]=eid++;
        //以下适用于无向图
        swap(from,to);
        e[eid].next=p[from];
        e[eid].v=to;
        e[eid].cost=cost;
        p[from]=eid++;
    }
}
void print(long End)
{
    //若为lmax 则不可达
    printf("%ld\n",Dis[End]);    
}
void SPF()
{
    init();
    long Start,End;
    scanf("%ld %ld",&Start,&End);
    Dis[Start]=0;
    vist[Start]=true;
    q.push(Start);
    while (!q.empty())
    {
        long t=q.front();
        q.pop();
        vist[t]=false;
        long j;
        for (j=p[t];j!=-1;j=e[j].next)
        {
            long w=e[j].cost;
            if (w+Dis[t]<Dis[e[j].v])
            {
                Dis[e[j].v]=w+Dis[t];
                if (!vist[e[j].v])
                {
                    vist[e[j].v]=true;
                    q.push(e[j].v);
                }
            }
        }
    }
    print(End);
}
int main()
{
    while (scanf("%ld %ld",&m,&n)!=EOF)
    {
        SPF();
    }
    return 0;

}

╝⑧

最短路径算法之Floyd-Warshall算法

§3 Floyd-Warshall算法

╔

Floyd-Warshall算法是解决任意两点间的最短路径的算法，可以处理有向图或负权值的最短路径问题，同时也被用于计算有向图的传递闭包。算法的时间复杂度为O(n³)，空间复杂度为O(n²)。

Floyd-Warshall算法的原理是动态规划。

设 $D_{i,j,k}$ 为从 $i$ 到 $j$ 的只以 $(1..k)$ 集合中的节点为中间節点的最短路径的长度。

若最短路径经过点k，则 $D_{i,j,k}=D_{i,k,k-1}+D_{k,j,k-1}$ ；
若最短路径不经过点k，则 $D_{i,j,k}=D_{i,j,k-1}$ 。

因此， $D_{i,j,k}=\mbox{min}(D_{i,k,k-1}+D_{k,j,k-1},D_{i,j,k-1})$ 。

在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。

╝⑨

Floyd-Warshall算法实现

╔

  for(int k =1 ;  k <= n ; k ++ ){
      for(int i =1 ; i<= n ; i++){
          for(int j =1 ;j<=n;j++){
                 dist[ i ][ j ]= min( dist[ i ][ j ],dist[ i ][ k ]+dist[ k ][ j ] );      
            }
       }
  }

如果dist[i][k]或者dist[k][j]不存在，程序中用∞代替。

真正的Floyd算法是一种基于DP(Dynamic Programming)的最短路径算法。

设图G中n 个顶点的编号为1到n。令c [i, j, k]表示从i 到j 的最短路径的长度，其中k 表示该路径中的最大顶点，也就是说c[i,j,k]这条最短路径所通过的中间顶点最大不超过k。因此，如果G中包含边<i, j>，则c[i, j, 0] =边<i, j> 的长度；若i= j ，则c[i,j,0]=0；如果G中不包含边<i, j>，则c (i, j, 0)= +∞。c[i, j, n] 则是从i 到j 的最短路径的长度。

对于任意的k>0，通过分析可以得到：中间顶点不超过k 的i 到j 的最短路径有两种可能：该路径含或不含中间顶点k。若不含，则该路径长度应为c[i, j, k-1]，否则长度为 c[i, k, k-1] +c [k, j, k-1]。c[i, j, k]可取两者中的最小值。

状态转移方程：c[i, j, k]=min{c[i, j, k-1], c [i, k, k-1]+c [k, j, k-1]}，k＞0。

这样，问题便具有了最优子结构性质，可以用动态规划方法来求解。

#include <iostream>
 2 using namespace std;
 3 
 4 const int INF = 100000;
 5 int n=10,map[11][11],dist[11][11][11];
 6 void init(){
 7     int i,j;
 8     for(i=1;i<=n;i++)
 9         for(j=1;j<=n;j++)
10             map[i][j]=(i==j)?0:INF;
11     map[1][2]=2,map[1][4]=20,map[2][5]=1;
12     map[3][1]=3,map[4][3]=8,map[4][6]=6;
13     map[4][7]=4,map[5][3]=7,map[5][8]=3;
14     map[6][3]=1,map[7][8]=1,map[8][6]=2;
15     map[8][10]=2,map[9][7]=2,map[10][9]=1;
16 }
17 void floyd_dp(){
18     int i,j,k;
19     for(i=1;i<=n;i++)
20         for(j=1;j<=n;j++)
21             dist[i][j][0]=map[i][j];
22     for(k=1;k<=n;k++)
23         for(i=1;i<=n;i++)
24             for(j=1;j<=n;j++){
25                 dist[i][j][k]=dist[i][j][k-1];
26                 if(dist[i][k][k-1]+dist[k][j][k-1]<dist[i][j][k])
27                     dist[i][j][k]=dist[i][k][k-1]+dist[k][j][k-1];
28             }
29 }
30 int main(){
31     int k,u,v;
32     init();
33     floyd_dp();
34     while(cin>>u>>v,u||v){
35         for(k=0;k<=n;k++){
36             if(dist[u][v][k]==INF) cout<<"+∞"<<endl;
37             else cout<<dist[u][v][k]<<endl;
38         }
39     }
40     return 0;
41 }

╝⑨

最短路径算法之Johnson算法

§4 Johnson算算法

Johson算法是目前最高效的在无负环可带负权重的网络中求所有点对最短路径的算法. Johson算法是Bellman-Ford算法, Reweighting(重赋权重)和Dijkstra算法的大综合. 对每个顶点运用Dijkstra算法的时间开销决定了Johnson算法的时间开销. 每次Dijkstra算法(d堆PFS实现)的时间开销是O( E * lgd(V) ). 其中E为边数, V为顶点数, d为采用d路堆实现优先队列ADT. 所以, 此种情况下Johnson算法的时间复杂度是O( V * E * lgd(V) )。

Johnson算法具体步骤（翻译自wikipedia）：

╔

1.初始化，把一个node q添加到图G中，使node q 到图G每一个点的权值为0。

2.使用Bellman-Ford算法，从源点为q，寻找每一个点 v从q到v的最短路径h(v)，如果存在负环的话，算法终止。

3.使用第2步骤中Bellman-Ford计算的最短路径值对原来的图进行reweight操作（重赋值）：边<u,v>的权值w(u,v)，修改成w(u,v)+h(u)-h(v)。

4.最后，移去q，针对新图（重赋值之后的图）使用Dijkstra算法计算从每一个点s到其余另外点的最短距离。

╝⑩

Johnson算法实现：

╔

#include "stdafx.h"
#include<iostream>
#define Infinity 65535
#define MAX 100
using namespace std;
//边尾节点结构体
struct edgeNode
{
int no;//节点序号
int weight; //此边权值
edgeNode *next; //下一条邻接边
};
//节点信息
struct vexNode
{
char info; //节点序号
edgeNode *link; //与此节点为首节点的边的尾节点链表
};
//优先队列元素结构体
struct PriQue
{
int no; //节点元素序号
int weight; //源点到此节点的权值
};
//节点数组
vexNode adjlist[MAX];
//添加一个序号为0节点到其他各节点的最小权值
int d[MAX];
//源点到各节点的最小权值
int lowcost[MAX];
//各节点对间的最小权值
int mincost[MAX][MAX];
//优先队列
PriQue queue[2*MAX];
//建立图的邻接表
void createGraph(vexNode *adjlist,int n,int e)
{
int i;
cout<<"请输入这些节点的信息："<<endl;
for(i=1;i<=n;i++)
{
cout<<"节点"<<i<<"的名称:";
cin>>adjlist[i].info;
adjlist[i].link = NULL;
}
cout<<"请输入这些边的信息："<<endl;
int v1,v2;
edgeNode *p1;
int weight1;
for(i=1;i<=e;i++)
{
cout<<"边"<<i<<"的首尾节点：";
cin>>v1>>v2;
cout<<"请输入此边的权值：";
cin>>weight1;
p1 = (edgeNode*)malloc(sizeof(edgeNode));
p1->no = v2;
p1->weight = weight1;
p1->next = adjlist[v1].link;
adjlist[v1].link = p1;
}
//添加节点0，到每一个节点的距离都是0
adjlist[0].info ='0';
adjlist[0].link = NULL;
for(i=n;i>=1;i--)
{
d[i] = 0;
p1 = (edgeNode*)malloc(sizeof(edgeNode));
p1->no = i;
p1->weight = 0;
p1->next = adjlist[0].link;
adjlist[0].link = p1;
}
}
//bellman_ford算法求节点0到其他各节点的最短距离
bool bellman_ford(vexNode *adjlist,int *d,int n)
{
int i,j;
d[0] = 0;
edgeNode *p1;
for(j=1;j<=n;j++)
{
for(i=0;i<=n;i++)
{
p1= adjlist[i].link;
while(p1 != NULL)
{
if(d[p1->no]>d[i]+p1->weight)
d[p1->no] = d[i] + p1->weight;
p1 = p1->next;
}
}
}
for(i=0;i<=n;i++)
{
p1= adjlist[i].link;
while(p1 != NULL)
{
if(d[p1->no]>d[i]+p1->weight)
return false;
p1 = p1->next;
}
}
return true;
}
//johnson算法中，需要对每一条边重新赋权值产生非负的权
void G_w_to_G1_w1(int *d,const int n)
{
int i;
edgeNode *p1;
for(i=0;i<=n;i++)
{
p1= adjlist[i].link;
while(p1 != NULL)
{
p1->weight = p1->weight + d[i] - d[p1->no];
p1 = p1->next;
}
}
}
//保持优先队列的优先性，以指定源点到每一点的最少距离为关键字
void keep_heap(PriQue *queue,int &num,int i)
{
int smallest = i;
int left = 2*i,right = 2*i+1;
if(left<=num&&queue[left].weight<queue[i].weight)
smallest = left;
if(right<=num&&queue[right].weight<queue[smallest].weight)
smallest = right;
if(smallest != i)
{
PriQue q = queue[smallest];
queue[smallest] = queue[i];
queue[i] = q;
keep_heap(queue,num,smallest);
}
}
//插入一个元素到优先队列中，并保持队列优先性
void insert_heap(PriQue *queue,int &num,int no,int wei)
{
num += 1;
queue[num].no = no;
queue[num].weight = wei;
int i = num;
while(i>1&&queue[i].weight<queue[i/2].weight)
{
PriQue q1;
q1 = queue[i/2];
queue[i/2] = queue[i];
queue[i] = q1;
i = i/2;
}
}
//取出队列首元素
PriQue heap_extract_min(PriQue *queue,int &num)
{
if(num<1)
return queue[0];
PriQue que = queue[1];
queue[1] = queue[num];
num = num -1;
keep_heap(queue,num,1);
return que;
}
//dijkstra算法求节点i到其他每一个节点的最短距离
void dijkstra(vexNode *adjlist,PriQue * queue,int i,const int n,int &num)
{
int v = i;
//lowcost[v] = 0;
int j;
for(j=1;j<n;j++)
{
edgeNode *p1 = adjlist[v].link;
while(p1 != NULL)
{
if(lowcost[p1->no] > lowcost[v] + p1->weight)
{
lowcost[p1->no] = lowcost[v] + p1->weight;
insert_heap(queue,num,p1->no,lowcost[p1->no]);
}
p1 = p1->next;
}
v = heap_extract_min(queue,num).no;
if(v==0)
{
cout<<"队列中没有节点！"<<endl;
return;
}
}
}

int _tmain(int argc, _TCHAR* argv[])
{
int cases;
cout<<"请输入案例的个数：";
cin>>cases;
//用队列0元素作为哨兵，如果队列中没有元素，则返回队列0元素
queue[0].no = 0;
queue[0].weight = 0;
while(cases--)
{
int n,e;
cout<<"请输入节点数：";
cin>>n;
cout<<"请输入边数：";
cin>>e;
//队列中的元素，初始为0
int num = 0;
int i,j;
//创建邻接表
createGraph(adjlist,n,e);
cout<<endl;
memset(d,Infinity,sizeof(d));
//bellman_ford算法求节点0到其他各节点的最短距离
bool flag = bellman_ford(adjlist,d,n);
if(!flag)
{
cout<<"此图存在负回路，不正确！"<<endl;
continue;
}
//johnson算法中，需要对每一条边重新赋权值产生非负的权
G_w_to_G1_w1(d,n);
//运用dijkstra算法求得每一对节点间的最短距离
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
lowcost[j] = Infinity;
lowcost[i] =0;
dijkstra(adjlist,queue,i,n,num);
//重新把原值赋值回来，因为在函数G_w_to_G1_w1()中改变过
for(j=1;j<=n;j++)
mincost[i][j] = lowcost[j] + d[j] - d[i];
}
cout<<"下面输出每一对顶点之间的最短距离："<<endl;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
cout<<"顶点("<<i<<":"<<adjlist[i].info<<")到顶点("<<j<<":"<<adjlist[j].info<<")的最短距离为："<<mincost[i][j]<<endl;
}
}
system("pause");
return 0;
}

╝⑩+1

§5 问题归约

╔

对于两个问题A和B，如果使用求解B的一个算法来开发一个求解A的算法，且最坏的情况下算法总时间不会超过最坏情况下求解B的算法运行时间的常量倍，则称问题A可归约（reduce)为问题B。

1.传递闭包问题可归约为有非负权值的所有对最短路径问题。

给定两点u和v，有向图中从u到v存在一条路径，当且仅当网中从u到v的路径长度非零。

2.在边权没有限制的网中，（单源点或所有对）最长路径和最短路径问题是等价的。

3.作业调度问题可归约为差分约束问题。

4.有正常数的差分约束问题等价于无环网中的单源点最长路径。

5.带有截止期的作业调度问题可归约为（允许带有负权值的）最短路径问题。

╝⑩+2

§6 最短路径的扩展与应用