(图) – Dijkstra和Floyd算法

1.Dijkstra算法

逻辑结构:


对于一个无向有权图(邻接矩阵存储的):

索引值 0 1 2 3 4 5 6 7 8
A: 0 0 4 10 3
B: 1 4 0
C: 2 10 0 55
D: 3 0 1 7
E: 4 3 1 0 1
F: 5 1 0 1
G: 6 1 0 1
H: 7 1 0 1
I: 8 55 7 1 0

注意:邻接矩阵存储的格式:二维数组martix[size][size] ,注意每个顶点对应一个名称,这个对应关系存储在vector names={A,B,C,D,E,F,G,H,I} 中,
这个算法的关键就是要计算从V0开始到最后一个顶点的位置,但是这是需要一步一步求的,每一步求出最权最小的路径,然后加一组合就可以得出最短的的路径(但是要注意随时会出现的替换的问题)
如下图所示
1.1 开始
黄色底色代表出发点,灰色底色代表被访问的顶点,灰色连线表示访问的边
第一步: 求出从V0出发所能到的具有最小权的顶点(在这个图上看得出是V4)所以,计算得到V0->V4=3(注意我们需要把这个最近一次搜索的顶点保存,以便从这个已经最小的顶点开始进行下一次的搜索,同时也需要设置一个保存被访问的顶点的变量)

第二步:以V4为起点搜索我们V0->V4->V5=3+1=4和V0->V4->V3=3+1=4可以发现二者具有此相同的权总和。所以我们先从考虑V3的情况

第三步:以V3位起点搜索。从图中V0->V4->V3->V8=4+7=11而在第三步中V0->V4->V5->V6->V7->V8=3+1+1+1+1=7<11所以明显后者是一个总权最小的路径 算法的实现: 首先我们需要一个辅助的函数:这个函数用于输出顶点Vv的所有路径的数组(用vector存储)。例如若v=0 那么vec{∞,4,10,∞,3,∞,∞,∞,∞}(注意当V0->V0的时候保存的是0但是在搜索的时候认为是∞)





1.2 实现它!

1.2.1 谈一谈我的想法:

每一步搜索我总是从一直搜索从有最小的权(从V0->Vw),然后获取这个w 保存为k ,标志finalPath[k]=1被设置用于标记已经搜索的顶点。然后从Vk开始搜索能到达Vw(第二个for的)的比从V0->Vw的最小的权的总和(当然从Vk->Vw的权还要加上我获取的那个最小的前驱的权总和min)。然后需要设置Patharc[w]=k来设置新的前驱 同时更新权的总和。这就有助于解决从V4(E)->V3(D)->V8(I)和V4->V5(F)->...->V8

更新:补充一句,这个算法是DP类型,我之前一直没有看出来实际上就是pathweight[i]表示的就是从v0到i的最小的路径长度,pathweight[i]=min { pathweight[i] , pathweight[k] + edge(k,i) }。其中edge(k,l)就是中间节点k到l的路径长度。每次设置完后需要重新确定是否存在从k到j(0<=j<size)有一个比从v0到j的最短的距离,如果有的话就可以更新它。
1.2.2 需要的辅助的函数:

//根据两个顶点的位置 返回边的权
	int getWeight(int srcindex,int destindex)
	{
		if (martix)
		{
			if (srcindex >= 0 && destindex >= 0 && srcindex < size && destindex < size)
			{
				return martix[srcindex][destindex];
			}
		}
	}
//这个用于初始化从v开始到任意一个可以连接的顶点的权值
	void dijkstra_setWeightSummary(int v, vector<int> &vec)
	{
		if (v >= 0 && v < size)
		{
			for (int u = 0; u < size; ++u)
			{
				//if (martix[v][u] == SAME)
				//{
				//	vec.push_back(NOEDGE);
				//}
				//else
				//{
					vec.push_back(martix[v][u]);
				//}
			}
		}
	}

1.2.3 这个是核心的函数

void do_dijkstra(int v0,vector<int> &Patharc,vector<int> &PathWeights)
	{
		
		vector<int> finalPath(size);//标志信息 保存前驱顶点
		int v, w, k, min;//
		//初始化数据 patharc保存的是从v0->vi的路径数组 pathweight表示的v0点有连线的顶点+权值
		for (v = 0; v < size; ++v)
		{
			finalPath[v] = 0;
			Patharc.push_back(0);
		}
		dijkstra_setWeightSummary(v0,PathWeights);//这个从起始点开始 吧从v0能到的点的边设置权值
		PathWeights[0] = 0;//出事的v0->v0的权为0
		finalPath[v0] = 1;//这个表示v0这个路径被访问
		for (v = 0; v < size; ++v)
		{
			min = NOEDGE;//这个是最小的权值 w为第一个可能的节点
			for (w = 0; w < size; ++w)
			{
				if (!finalPath[w] && PathWeights[w] < min)
				{
					k = w;//这个k表示的就是第一个要被替换的位置(因为从V0到vw的权更小)
					min = PathWeights[w];//保存这个最小的权值 继续比较找到更小的位置
				}
			}
			finalPath[k] = 1;//目前找到的最小的权的目标点设为1 表示已经搜索了
			for (w = 0; w < size; ++w)
			{
				if (!finalPath[w]/*如果是0的话 表示这个位置可以替换 如果是1的话表示这个位置之前已经定下来了*/ && (min + getWeight(k, w) < PathWeights[w]))
				{
					PathWeights[w] = min + getWeight(k, w);
					Patharc[w] = k;//设置前驱节点 如果目标的权比之前得到地权要小的话。。更新那个最小权的点的前驱
				}
			}
		}
		//delete finalPath;
	}

1.2.4 几个解释:
Patharc是用来保存前驱节点的数组
PathWeight这个是保存从V0到对应节点的最小的权的和对的数组
finalPath当finalPath[w]=1的时候表示已经求出了从V0->Vw的最短路径 这是一个标志
v用于循环中表示指定的一个顶点
min表示的是从Vw起始点到权最小的顶点的权值(注意不是累加顶点和)
k便是找到当min被赋值时所对应的Vw的下标
w是表示Vw的下标的循环变量

1.2.5 模拟计算:
第一步:输入起始点的坐标为0

开始搜索 设置min=∞
开始从V1搜索从V0->V1的最小的权的大小,最终找到的是V4,此时的min=3,k=4
循环结束我们需要设置最短的路径为finalPath[4]=1 表示我们已经设搜索了这个顶点

第二个循环开始 这个循环的目的是修正当前的最短路径以及权的总和(从Vk开始到Vw(这个是新的w)的最短路径是否比现有的路径的总权和短)
首先要判断这个顶点是否已经被搜索到(防止走回头路),很显然finalPath[0]和finalPath[4]不为0 所以他们不会被在此修正。
这是会发现从从V0->V3是没有路通的,所以他的值PathWeights[3]为无穷符号自然满足min(3)+getWeight(V4,V3)的值 =3+1=4
所以PathWeights和Patharc会被更改为

但是还要注意还有min+getWeight(V4,V5)也满足条件 所以还得改

然后,,就没然后了。
第二步开始啦!
这时的v=2啦。
我们还要寻找最小的从V0的到各个点的权最小的值,我们找到了min=4,k=1(注意我们排除了已搜索项目)
所以finalPath的索引为4、0和1不会再参与第二次修正

第二个循环:开始搜索以V1为起点的更短路径 当然是什么都搜索不到…
所以第三步开始:
这是v=3
min=4,k=3

再以V3为起点搜索最短的顶点,存在一个min+getWeight(V3,V8)=4+7 < ∞(V0和V8没有联通)

第四步

接着从V5开始搜索最短的路径 发现min+getWeight(V5,V6)=4+1<∞

第五步:
v=5,min=5,k=6

这个以此类推,min+getWeight(V6,V7)=5+1<∞

第六步:
v=6,min=6,k=1

同理,min+getWeight(V7,V8)=6+1<11

第七步:v=7,min=7, k=8

这个以此类推,没有什么顶点可供V8访问
所以,第八步
v=8,min=10,k=2
同样的道理,也没有什么顶点供V2访问 所以

第九步:退出最外层循环,函数结束

所以从V0(A)开始的到V8(I)的最短路径就是A->E->F->G->H->I 权的总和为7

效果如下图:

更新:注意Patharc[i]保存的就是从v0->i的各个路径上的前驱结点,随所以我的接口部分只需要将Patharc中的内容打逆序印出来就可以了。

1.1 Dijkstra的堆优化

想想,每次都会有个循环,这个循环就是要找到一个未被访问且从v0到k总是最小的点。对于除v0的点,其他的点都是一定要被访问的,所以为何不使用最小对来优化呢?(反正每次取出的总是最短的)。

void do_dijkstra_heap(int v0,vector<int> &pre,vector<int> &weight)
	{
		typedef std::pair<int, int> P;//P类型是保存从v0到该点second的最短的距离 每次从v0搜索路径的时候总是可以先进行搜索
		std::priority_queue<P, std::vector<P>, std::greater<P>> que;//保存距离的最小堆.
		weight[v0] = 0;//weight[i]是保存从v0出发到顶点为i的距离
		que.push(P(0, v0));
		while (!que.empty())
		{
			P p = que.top();
			que.pop();//弹出
			int v = p.second;//v是最短的点
			if (p.first > weight[v])
				continue;//如果这个边还要大 就不要再继续比较了 这个点就要不得,因为他是更新之前的从i->v的最大值(包括没有路径)
			//定义weight[i]表示v0->i的距离 weight[v]=min(weight[v],weight[w]+weight(w->v))
			for (int w = 0; w < size; ++w)
			{
				if (martix[v][w] != NOEDGE && martix[v][w] != SAME)//如果从v->w有捷径可走的话
				{
					int weight_vw = martix[v][w];
					if (weight[w] > weight[v] + weight_vw)//v0->w 和v0->v(认为是最短的)->w哪一个更短?
					{
						weight[w] = weight[v] + weight_vw;
						pre[w] = v;//前驱
						que.push(P(weight[w], w));//把这个最小的权值放进去
					}
				}
			}


		}
	}

2.Floyd算法

这个算法更厉害 可以算出任意一点的与图上任意一点的最小权的路径,同时也可以精确地算出路径。这个也挺厉害的。

  • 2.1 例子:

首先来个简单的

设这个权表为D-1

索引 0 1 2
A: 0 0 1 2
B: 1 1 0 10
C: 2 2 10 0

我们可以先搜索V1->V0->V2的最小权的路径D-1[1][0]->D-1[0][2]=2+1=3而直接从V1->V2的权总和为D-1[1][2]=10

这么一来,D-1[1][0]->D-1[0][2]< D-1[1][2]

那么就有一个判断条件:D0[v][w]=min{ D-1[v][w] , D-1[v][0]+D-1[0][w] }(动态规划算法)

例子就到这里,我们来看之前的那个图

他的邻接矩阵的数据结构如下:

这个表示的是第一次的权表:D-1

索引值 0 1 2 3 4 5 6 7 8
A: 0 0 4 10 3
B: 1 4 0
C: 2 10 0 55
D: 3 0 1 7
E: 4 3 1 0 1
F: 5 1 0 1
G: 6 1 0 1
H: 7 1 0 1
I: 8 55 7 1 0

我们还需要P-1  是用来存储路径。首先初始化一下这样:

索引值 0 1 2 3 4 5 6 7 8
A: 0 0 1 2 3 4 5 6 7 8
B: 1 0 1 2 3 4 5 6 7 8
C: 2 0 1 2 3 4 5 6 7 8
D: 3 0 1 2 3 4 5 6 7 8
E: 4 0 1 2 3 4 5 6 7 8
F: 5 0 1 2 3 4 5 6 7 8
G: 6 0 1 2 3 4 5 6 7 8
H: 7 0 1 2 3 4 5 6 7 8
I: 8 0 1 2 3 4 5 6 7 8

在我的例子之中没有使用动态分配的二维数组,而是用了是vector<vector<int>> 存储,其实也没什么,主要是方便。

D-1[k][w]表示的是从Vk->Vw的权,D-1[v][w]表示的是从Vv->Vw的权。对于无向图,权D-1[w][v]= D-1[v][w]表示的就是Vw->Vv所以他们的权之和为Vk->Vv的权然后与Vk->Vv(直接)的权值之和比较。如果小的话,更新D-1[v][w]。注意我们讨论的是无向图,但是对于有向图的话,D-1[v][w]为∞(不会有那两个均不为∞能大于∞),这个∞总是会被替换的(其他路径),但是D-1[w][v]可能是一个别的值。仅仅是方向的区别。别忘了我们需要更新P数组的值。所以说白了所有的点需要从Vk中转

//弗洛伊德算法
	void do_floyd(vector<vector<int>> &P, vector<vector<int>> &D)
	{
		for (int i = 0; i < size; ++i)
		{
			dijkstra_setWeightSummary(i, D[i]);
			for (int j = 0; j < size; ++j)
			{
				P[i].push_back(j);
			}
		}
		int v, w, k;
		//v是起始顶点左边 w是结束点坐标 k是中转点坐标 所有的顶点都会在Vk中转
		for (k = 0; k < size; ++k)
		{
			for (v = 0; v < size; ++v)
			{
				for (w = 0; w < size; ++w)
				{
					if (D[v][w] > D[v][k] + D[k][w]) /*D[v][w] 表示的是整个二维数组需要搜索的范围 D[v][k]表示的是以k列的一列 D[k][w]表示以k为一行*/
					{
						
						D[v][w] = D[v][k] + D[k][w];
						P[v][w] = P[v][k];
					}
				}
			}
		}
	}

2.2 模拟计算:

注意:加粗下划线表示的是要替换的位置

第一步:k=0

D:

发现:

D[1][2]=∞而D[1][0]+D[0][2]=14
D[1][4]=∞而D[1][0]+D[0][3]=4+3=7
D[2][1]=∞而D[2][0]+D[0][1]=14
D[2][4]=∞而D[2][0]+D[0][4]=13
D[4][1]=∞而D[4][0]+D[0][1]=7
D[4][2]=∞而D[4][0]+D[0][2]=13

同时上述被修改的位置所对应的P[v][w]要被改为P[v][k]

P[1][2]=P[1][0]=0

P[1][4]=P[1][0]=0

P[2][1]=0

P[2][4]=0

P4][1]=0

P[4][2]=0

从k=1到k=8的关系可以此类推。。

当k=8时:D:

索引值 0 1 2 3 4 5 6 7 8
A: 0 0 4 10 4 3 4 5 6 7
B: 1 4 0 14 8 7 8 9 10 11
C: 2 10 14 0 14 13 14 15 16 17
D: 3 4 8 14 0 1 2 3 4 5
E: 4 3 7 13 1 0 1 2 3 4
F: 5 4 8 14 2 1 0 1 2 3
G: 6 5 9 15 3 2 1 0 1 2
H: 7 6 10 16 4 3 2 1 0 1
I: 8 7 11 17 5 4 3 2 1 0

P:

索引值 0 1 2 3 4 5 6 7 8
A: 0 0 1 2 4 4 4 4 4 4
B: 1 0 1 0 0 0 0 0 0 0
C: 2 0 0 2 3 0 5 6 7 8
D: 3 4 4 4 3 4 4 4 4 4
E: 4 0 0 0 3 4 5 5 5 5
F: 5 4 4 4 4 4 5 6 6 6
G: 6 5 5 5 5 5 5 6 7 7
H: 7 6 6 6 6 6 6 6 7 8
I: 8 7 7 7 7 7 7 7 7 8

2.3 我们怎么获得路径呢?

例如我们求从V0->V8的路径: P[0][8]=4 表示我们需要经过V4 P[4][8]=5 表示经过V5 P[5][8]=6表示要经过V6 P[6][8]=7表示经过V7 P[7][8]=8到达终点,结束。8

所以路径为V0(A)->V4(E)->V5(F)->V6(G)->V7(H)->V8(I) 最小的权为D[0][8]=7 每一边对应的权为D[ i ] [ P[ i ][8] ], i为0-->P[0][8]=4-->P[4][8]=5-->P[5][8]=6-->P[6][8]=7-->P[7][8]=8 结束 依次得3+1+1+1+1 = 7

可以求任意两点之间的距离

3. 附上两个算法的类的接口:

void Find_MinPath_Dijkstra()
	{
		vector<int> arc, weight;
		int v0;
		cout << "请输入起始点:(0~" << size - 1 << "):";
		cin >> v0;
		do_dijkstra(v0, arc, weight);
		for (int i = 0; i < size; ++i)
		{
			if (i == v0)
				continue;
			std::cout << "从" << names[v0].name << "到" << names[i].name << "的最小的权为:" << weight[i] << ", 路径为:"<<names[v0].name<<"->";
			int vex = i;
			std::stack<int> ids;
			while (arc[vex] != v0)
			{
				ids.push(arc[vex]);
				vex = arc[vex];//因为我每次加入的是前驱 所以只要vex与这arc[vex]是前驱关系就可以了
			}
			while (!ids.empty())
			{
				std::cout << names[ids.top()].name << "->";
				ids.pop();
			}
			std::cout << names[i].name << std::endl;
		}
	}
	void Find_MinPath_Floyd()
	{
		vector<vector<int>> arc(size), weight(size);
		int v0,vx;
		cout << "请输入起始点和终止点:(0~" << size - 1 << "):";
		cin >> v0>>vx;
		do_floyd(arc, weight);
		if (v0 >= 0 && v0 < size && vx >= 0 && vx < size)
		{
			int beg = v0;
			int wei = v0;
			while (beg != vx)
			{
				wei= arc[beg][vx];
				cout << names[beg].name << "--("<<weight[beg][wei]<<")-->";
				beg = wei;
			}
			//记得最后一个元素
			cout << names[beg].name << endl;
		}
	}
void Find_MinPath_Dijkstra_Heap()//堆优化的Dijkstra算法
	{
		int v0;
		std::cout << "请输入起点:";
		std::cin >> v0;
		std::vector<int> pre(size),weight(size,NOEDGE);
		do_dijkstra_heap(v0, pre,weight);
		//打印前驱
		for (int i = 0; i < size; ++i)
		{
			if (i != v0)
			{
				std::stack<int> pathpoint;
				pathpoint.push(i);
				int k = i;
				while (pre[k] != v0)
				{
					pathpoint.push(pre[k]);
					k = pre[k];
				}
				pathpoint.push(v0);
				while (!pathpoint.empty())
				{
					std::cout << names[pathpoint.top()].name;
					pathpoint.pop();
					if (!pathpoint.empty())
						std::cout << "->";
				}
				std::cout << " min path weight : " << weight[i];
				std::cout << std::endl;
			}
		}
	}

注意,我的这个算法是在类内实现的,所以可能代码不太全。size表示的是顶点格式names是保存索引对应的顶点名称,martix是size*size的二维数组用来保存顶点和边的关系 names的元素类型为vertex,该struct拥有一个name的string成员

4. 参考:

4.1 《大话数据结构》