博客

z最短路合集（贝尔曼福德算法+迪杰斯克拉算法+弗洛伊德算法）

  • Post author:
  • Post category:其他




Dijkstra算法







是处理单源最短路径的有效算法，但它局限于边的权值非负的情况，若图中出现权值为负的边，Dijkstra算法就会失效，求出的最短路径就可能是错的。这时候，就需要使用其他的算法来求解最短路径，

Bellman-Ford算法

就是其中最常用的一个。该算法由美国数学家理查德•贝尔曼（Richard Bellman, 动态规划的提出者）和小莱斯特•福特（Lester Ford）发明。Bellman-Ford算法的流程如下：



给定图G(V, E)（其中V、E分别为图G的顶点集与边集），源点s，


  • 数组Distant[i]记录从源点s到顶点i的路径长度，初始化数组Distant[n]为, Distant[s]为0；


  • 以下操作循环执行至多n-1次，n为顶点数：

    对于每一条边e(u, v)，如果Distant[u] + w(u, v) < Distant[v]，则另Distant[v] = Distant[u]+w(u, v)。w(u, v)为边e(u,v)的权值；

    若上述操作没有对Distant进行更新，说明最短路径已经查找完毕，或者部分点不可达，跳出循环。否则执行下次循环；

  • 为了检测图中是否存在负环路，即权值之和小于0的环路。对于每一条边e(u, v)，如果存在Distant[u] + w(u, v) < Distant[v]的边，则图中存在负环路，即是说改图无法求出单源最短路径。否则数组Distant[n]中记录的就是源点s到各顶点的最短路径长度。


可知，

Bellman-Ford算法

寻找单源最短路径的时间复杂度为O(V*E).


首先介绍一下松弛计算。如下图：





松弛计算之前，点B的值是8，但是点A的值加上边上的权重2，得到5，比点B的值（8）小，所以，点B的值减小为5。这个过程的意义是，找到了一条通向B点更短的路线，且该路线是先经过点A，然后通过权重为2的边，到达点B。

当然，如果出现一下情况





则不会修改点B的值，因为3＋4>6。

Bellman－Ford算法可以大致分为三个部分

第一，初始化所有点。每一个点保存一个值，表示从原点到达这个点的距离，将原点的值设为0，其它的点的值设为无穷大（表示不可达）。

第二，进行循环，循环下标为从1到n－1（n等于图中点的个数）。在循环内部，遍历所有的边，进行松弛计算。

第三，遍历途中所有的边（edge（u，v）），判断是否存在这样情况：

d（v） > d (u) + w(u,v)

则返回false，表示途中存在从源点可达的权为负的回路。

之所以需要第三部分的原因，是因为，如果存在从源点可达的权为负的回路。则 应为无法收敛而导致不能求出最短路径。

考虑如下的图：



经过第一次遍历后，点B的值变为5，点C的值变为8，这时，注意权重为－10的边，这条边的存在，导致点A的值变为－2。（8＋ －10＝－2）



第二次遍历后，点B的值变为3，点C变为6，点A变为－4。正是因为有一条负边在回路中，导致每次遍历后，各个点的值不断变小。

在回过来看一下bellman－ford算法的第三部分，遍历所有边，检查是否存在d（v） > d (u) + w(u,v)。因为第二部分循环的次数是定长的，所以如果存在无法收敛的情况，则肯定能够在第三部分中检查出来。比如



此时，点A的值为－2，点B的值为5，边AB的权重为5，5 > -2 + 5. 检查出来这条边没有收敛。

所以，Bellman－Ford算法可以解决图中有权为负数的边的单源最短路径问。


个人感觉算法导论讲解很不错，把这一章贴出来和大家分享:






24.1 The Bellman-Ford algorithm


The


Bellman-Ford algorithm


solves the single-source shortest-paths problem in the general case in which edge weights may be negative. Given a weighted, directed graph

G

= (

V

,

E

) with source

s

and weight function

w

:

E

→

R

, the Bellman-Ford algorithm returns a boolean value indicating whether or not there is a negative-weight cycle that is reachable from the source. If there is such a cycle, the algorithm indicates that no solution exists. If there is no such cycle, the algorithm produces the shortest paths and their weights.


The algorithm uses relaxation, progressively decreasing an estimate

d

[

v

] on the weight of a shortest path from the source

s

to each vertex

v

∈

V

until it achieves the actual shortest-path weight

δ

(

s

,

v

). The algorithm returns TRUE if and only if the graph contains no negative-weight cycles that are reachable from the source.
 

BELLMAN-FORD(G, w, s)
1  INITIALIZE-SINGLE-SOURCE(G, s)
2  for i ← 1 to |V[G]| - 1
3       do for each edge (u, v) ∈ E[G]
4              do RELAX(u, v, w)
5  for each edge (u, v) ∈ E[G]
6       do if d[v] > d[u] + w(u, v)
7             then return FALSE
8  return TRUE



Figure 24.4

shows the execution of the Bellman-Ford algorithm on a graph with 5 vertices. After initializing the

d

and π values of all vertices in line 1, the algorithm makes |

V

| – 1 passes over the edges of the graph. Each pass is one iteration of the

for

loop of lines 2-4 and consists of relaxing each edge of the graph once. Figures 24.4(b)-(e) show the state of the algorithm after each of the four passes over the edges. After making |

V

|- 1 passes, lines 5-8 check for a negative-weight cycle and return the appropriate boolean value. (We’ll see a little later why this check works.)


（单击图片可以放大）


Figure 24.4: The execution of the Bellman-Ford algorithm. The source is vertex

s

. The

d

values are shown within the vertices, and shaded edges indicate predecessor values: if edge (

u, v

) is shaded, then π[

v

] =

u

. In this particular example, each pass relaxes the edges in the order (

t, x

), (

t, y

), (

t, z

), (

x, t

), (

y, x

), (

y, z

), (

z, x

), (

z, s

), (

s, t

), (

s, y

). (a) The situation just before the first pass over the edges. (b)-(e) The situation after each successive pass over the edges. The

d

and π values in part (e) are the final values. The Bellman-Ford algorithm returns TRUE in this example.


The Bellman-Ford algorithm runs in time

O

(

V E

), since the initialization in line 1 takes Θ(

V

) time, each of the |

V

| – 1 passes over the edges in lines 2-4 takes Θ(

E

) time, and the

for

loop of lines 5-7 takes

O

(

E

) time.


以下是


Bellman-Ford代码


:




复制代码


/*



* About:  Bellman-Ford算法

* Author: Tanky Woo

* Blog:   www.WuTianqi.com



*/

#include


<


iostream


>





using




namespace


std;



const




int


maxnum


=




100


;



const




int


maxint


=




99999


;



//


边，





typedef


struct


Edge{




int


u, v;


//


起点，重点







int


weight;


//


边的权值





}Edge;

Edge edge[maxnum];


//


保存边的值





int


dist[maxnum];


//


结点到源点最小距离








int


nodenum, edgenum, source;


//


结点数，边数，源点



//


初始化图





void


init()

{




//


输入结点数，边数，源点





cin


>>


nodenum


>>


edgenum


>>


source;



for


(


int


i


=


1


; i


<=


nodenum;


++


i)

dist[i]


=


maxint;

dist[source]


=




0


;



for


(


int


i


=


1


; i


<=


edgenum;


++


i)

{


cin


>>


edge[i].u


>>


edge[i].v


>>


edge[i].weight;



if


(edge[i].u


==


source)


//


注意这里设置初始情况





dist[edge[i].v]


=


edge[i].weight;

}

}



//


松弛计算





void


relax(


int


u,


int


v,


int


weight)

{




if


(dist[v]


>


dist[u]


+


weight)

dist[v]


=


dist[u]


+


weight;

}



bool


Bellman_Ford()

{




for


(


int


i


=


1


; i


<=


nodenum


–


1


;


++


i)



for


(


int


j


=


1


; j


<=


edgenum;


++


j)

relax(edge[j].u, edge[j].v, edge[j].weight);



bool


flag


=




1


;



//


判断是否有负环路







for


(


int


i


=


1


; i


<=


edgenum;


++


i)



if


(dist[edge[i].v]


>


dist[edge[i].u]


+


edge[i].weight)

{


flag


=




0


;



break


;

}



return


flag;

}



int


main()

{




//


freopen(“input3.txt”, “r”, stdin);





init();



if


(Bellman_Ford())



for


(


int


i


=




1


;i


<=


nodenum; i


++


)

cout


<<


dist[i]


<<


endl;



return




0


;

}



Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

Dijkstra算法

能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。


Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。


其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。



初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的

特殊路径

，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。


例如，对下图中的有向图，应用

Dijkstra算法

计算从源顶点1到其它顶点间最短路径的过程列在下表中。





Dijkstra算法的迭代过程：





主题好好理解上图！


以下是具体的实现(C/C++):
 

/***************************************
* About:    有向图的Dijkstra算法实现
* Author:   Tanky Woo
* Blog:     www.WuTianQi.com
***************************************/
 
#include <iostream>
using namespace std;
 
const int maxnum = 100;
const int maxint = 999999;
 
// 各数组都从下标1开始
int dist[maxnum];     // 表示当前点到源点的最短路径长度
int prev[maxnum];     // 记录当前点的前一个结点
int c[maxnum][maxnum];   // 记录图的两点间路径长度
int n, line;             // 图的结点数和路径数
 
// n -- n nodes
// v -- the source node
// dist[] -- the distance from the ith node to the source node
// prev[] -- the previous node of the ith node
// c[][] -- every two nodes' distance
void Dijkstra(int n, int v, int *dist, int *prev, int c[maxnum][maxnum])
{
	bool s[maxnum];    // 判断是否已存入该点到S集合中
	for(int i=1; i<=n; ++i)
	{
		dist[i] = c[v][i];
		s[i] = 0;     // 初始都未用过该点
		if(dist[i] == maxint)
			prev[i] = 0;
		else
			prev[i] = v;
	}
	dist[v] = 0;
	s[v] = 1;
 
	// 依次将未放入S集合的结点中，取dist[]最小值的结点，放入结合S中
	// 一旦S包含了所有V中顶点，dist就记录了从源点到所有其他顶点之间的最短路径长度
         // 注意是从第二个节点开始，第一个为源点
	for(int i=2; i<=n; ++i)
	{
		int tmp = maxint;
		int u = v;
		// 找出当前未使用的点j的dist[j]最小值
		for(int j=1; j<=n; ++j)
			if((!s[j]) && dist[j]<tmp)
			{
				u = j;              // u保存当前邻接点中距离最小的点的号码
				tmp = dist[j];
			}
		s[u] = 1;    // 表示u点已存入S集合中
 
		// 更新dist
		for(int j=1; j<=n; ++j)
			if((!s[j]) && c[u][j]<maxint)
			{
				int newdist = dist[u] + c[u][j];
				if(newdist < dist[j])
				{
					dist[j] = newdist;
					prev[j] = u;
				}
			}
	}
}
 
// 查找从源点v到终点u的路径，并输出
void searchPath(int *prev,int v, int u)
{
	int que[maxnum];
	int tot = 1;
	que[tot] = u;
	tot++;
	int tmp = prev[u];
	while(tmp != v)
	{
		que[tot] = tmp;
		tot++;
		tmp = prev[tmp];
	}
	que[tot] = v;
	for(int i=tot; i>=1; --i)
		if(i != 1)
			cout << que[i] << " -> ";
		else
			cout << que[i] << endl;
}
 
int main()
{
	freopen("input.txt", "r", stdin);
	// 各数组都从下标1开始
 
	// 输入结点数
	cin >> n;
	// 输入路径数
	cin >> line;
	int p, q, len;          // 输入p, q两点及其路径长度
 
	// 初始化c[][]为maxint
	for(int i=1; i<=n; ++i)
		for(int j=1; j<=n; ++j)
			c[i][j] = maxint;
 
	for(int i=1; i<=line; ++i)  
	{
		cin >> p >> q >> len;
		if(len < c[p][q])       // 有重边
		{
			c[p][q] = len;      // p指向q
			c[q][p] = len;      // q指向p，这样表示无向图
		}
	}
 
	for(int i=1; i<=n; ++i)
		dist[i] = maxint;
	for(int i=1; i<=n; ++i)
	{
		for(int j=1; j<=n; ++j)
			printf("%8d", c[i][j]);
		printf("\n");
	}
 
	Dijkstra(n, 1, dist, prev, c);
 
	// 最短路径长度
	cout << "源点到最后一个顶点的最短路径长度: " << dist[n] << endl;
 
	// 路径
	cout << "源点到最后一个顶点的路径为: ";
	searchPath(prev, 1, n);
}


Floyd-Warshall算法，简称

Floyd算法

，用于

求解任意两点间的最短距离，时间复杂度为O(n^3)。



使用条件&范围



通常可以在任何图中使用，包括有向图、带负权边的图。


Floyd-Warshall 算法用来找出每对点之间的最短距离。它需要用邻接矩阵来储存边，这个算法通过考虑最佳子路径来得到最佳路径。


1.注意单独一条边的路径也不一定是最佳路径。


2.从任意一条单边路径开始。所有两点之间的距离是边的权，或者无穷大，如果两点之间没有边相连。


对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。


3.不可思议的是，只要按排适当，就能得到结果。


伪代码:
 

// dist(i,j) 为从节点i到节点j的最短距离
For i←1 to n do
   For j←1 to n do
      dist(i,j) = weight(i,j) 
 
For k←1 to n do // k为“媒介节点”
   For i←1 to n do
      For j←1 to n do
         if (dist(i,k) + dist(k,j) < dist(i,j)) then // 是否是更短的路径？
            dist(i,j) = dist(i,k) + dist(k,j)


我们平时所见的

Floyd算法的一般形式

如下：
 

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


注意下第6行这个地方，如果dist[i][k]或者dist[k][j]不存在，程序中用一个很大的数代替。最好写成if(dist[i] [k]!=INF && dist[k][j]!=INF && dist[i][k]+dist[k][j]<dist[i][j])，从而防止溢出所造成的错误。 floyd算法的实现以及输出最短路径和最短路径长度，具体过程请看【

动画演示Floyd算法】。


代码说明几点：


1、A[][]数组初始化为各顶点间的原本距离，最后存储各顶点间的最短距离。


2、path[][]数组保存最短路径，与当前迭代的次数有关。初始化都为-1，表示没有中间顶点。在求A[i][j]过程中，path[i][j]存放从顶点vi到顶点vj的中间顶点编号不大于k的最短路径上前一个结点的编号。在算法结束时，由二维数组path的值回溯，可以得到从顶点vi到顶点vj的最短路径。


初始化A[][]数组为如下，即有向图的邻接矩阵。






完整的


实现代码


如下：
 

#include <iostream>
#include <string>   
#include <stdio.h>   
using namespace std;   
#define MaxVertexNum 100   
#define INF 32767   
typedef struct  
{   
    char vertex[MaxVertexNum];   
    int edges[MaxVertexNum][MaxVertexNum];   
    int n,e;   
}MGraph;   
 
void CreateMGraph(MGraph &G)   
{   
    int i,j,k,p;   
    cout<<"请输入顶点数和边数:";   
    cin>>G.n>>G.e;   
    cout<<"请输入顶点元素:";   
    for (i=0;i<G.n;i++)   
    {   
        cin>>G.vertex[i];   
    }   
    for (i=0;i<G.n;i++)   
    {   
        for (j=0;j<G.n;j++)   
        {   
            G.edges[i][j]=INF;   
            if (i==j)   
            {   
                G.edges[i][j]=0;   
            }   
        }   
    }      
    for (k=0;k<G.e;k++)   
    {   
        cout<<"请输入第"<<k+1<<"条弧头弧尾序号和相应的权值:";   
        cin>>i>>j>>p;   
        G.edges[i][j]=p;   
    }   
}   
void Dispath(int A[][MaxVertexNum],int path[][MaxVertexNum],int n);
 
void Floyd(MGraph G)
{
	int A[MaxVertexNum][MaxVertexNum],path[MaxVertexNum][MaxVertexNum];
	int i,j,k;
	for (i=0;i<G.n;i++)
	{
		for (j=0;j<G.n;j++)
		{
			A[i][j]=G.edges[i][j];
			path[i][j]=-1;
		}
	}
	for (k=0;k<G.n;k++)
	{
		for (i=0;i<G.n;i++)
		{
			for (j=0;j<G.n;j++)
			{
				if (A[i][j]>A[i][k]+A[k][j])
				{
					A[i][j]=A[i][k]+A[k][j];
					path[i][j]=k;
				}
			}
		}
	}
	Dispath(A,path,G.n);
}
 
void Ppath(int path[][MaxVertexNum],int i,int j)
{
	int k;
	k=path[i][j];
	if (k==-1)
	{
		return;
	}
	Ppath(path,i,k);
	printf("%d,",k);
	Ppath(path,k,j);
}
 
void Dispath(int A[][MaxVertexNum],int path[][MaxVertexNum],int n)
{
	int i,j;
	for (i=0;i<n;i++)
	{
		for (j=0;j<n;j++)
		{
			if (A[i][j]==INF)
			{
				if (i!=j)
				{
					printf("从%d到%d没有路径\n",i,j);
				}
			}
			else
			{
				printf("  从%d到%d=>路径长度:%d路径:",i,j,A[i][j]);
				printf("%d,",i);
				Ppath(path,i,j);
				printf("%d\n",j);
			}
		}
	}
}
 
int main()
{
	freopen("input2.txt", "r", stdin);
	MGraph G;
	CreateMGraph(G);
	Floyd(G);
	return 0;
}