当前位置:   article > 正文

最短路径算法——弗洛伊德(Floyd)算法_floyd算法求最短路径

floyd算法求最短路径
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接: https://blog.csdn.net/qq_30091945/article/details/77964810

概述

在这篇博客中我主要讲解最短路径算法中的Floyd算法,这是针对多源最短路径的一个经典算法。对于单源最短路径算法请详见我的另一篇博客:最短路径算法(上)——迪杰斯特拉(Dijikstra)算法

弗洛伊德(Floyd)算法是解决任意两点间的最短路径的一种算法,可以正确处理有向图或有向图或负权(但不可存在负权回路)的最短路径问题,同时也被用于计算有向图的传递闭包。

算法思想与过程

(一)算法思想:
Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话,首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题,我们需要为这个目标重新做一个诠释(这个诠释正是动态规划最富创造力的精华所在)。

从任意节点i到任意节点j的最短路径不外乎2种可能,一是直接从i到j,二是从i经过若干个节点k到j。所以,我们假设Dis(i,j)为节点u到节点v的最短路径的距离,对于每一个节点k,我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立,如果成立,证明从i到k再到j的路径比i直接到j的路径短,我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j),这样一来,当我们遍历完所有节点k,Dis(i,j)中记录的便是i到j的最短路径的距离。

(二)算法过程
1)首先把初始化距离dist数组为图的邻接矩阵,路径数组path初始化为-1。其中对于邻接矩阵中的数首先初始化为正无穷,如果两个顶点存在边则初始化为权重   
2)对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是就更新它。
状态转移方程为
如果 dist[i][k]+dist[k][j] < dist[i][j]
则dist[i][j] = dist[i][k]+dist[k][j]

//Floyd算法(多源最短路径算法) 
bool Floyd(){
	for(int k = 1 ; k < this->Nv+1 ; k++){	//k代表中间顶点 
		for(int i = 1  ; i < this->Nv+1 ; i++){//i代表起始顶点 
			for(int j = 1 ; j < this->Nv+1 ; j++){//j代表终点 
				if(this->dist[i][k] + this->dist[k][j] < this->dist[i][j]){
					this->dist[i][j] = this->dist[i][k] + this->dist[k][j];
					if(i == j && this->dist[i][j] < 0){//发现了负值圈 
						return false;
					}
					this->path[i][j] = k;
				}					
			}
		}
	}
	return true; 
}

   
   
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

例子

我们用如下图结构来演示Floyd算法:
这里写图片描述
全部代码为:

#include <iostream>
#include <cstring>
#include <stack>
#include <queue>
using namespace std;
  • 1
  • 2
  • 3
  • 4
  • 5

const int MAX = 65535;

class Graph{
private:
int** G; // 邻接矩阵
int** dist; // 距离数组
int** path; // 路径数组
int Nv; // 顶点数
public:
//构造函数
Graph(int nv, int ne){
this->Nv = nv;
G = new int*[nv+1];
dist = new int*[nv+1];
path = new int*[nv+1];
for(int i = 0 ; i < nv+1 ; i++){
G[i] = new int[nv+1];
dist[i] = new int[nv+1];
path[i] = new int[nv+1];
memset(path[i],-1,sizeof(path[0][0])*(nv+1));
for(int j = 0 ; j < nv+1 ; j++){
this->G[i][j] = this->dist[i][j] = MAX;
}
this->G[i][i] = this->dist[i][i] = 0;
}
cout<<“请输入边与权重:”<<endl;
for(int i = 0 ; i < ne ; i++){
int v1,v2,weight;
cin>>v1>>v2>>weight;
this->G[v1][v2] = this->G[v2][v1] = weight;
this->dist[v1][v2] = this->dist[v2][v1] = weight;
}
}

	//Floyd算法(多源最短路径算法) 
	bool Floyd(){
		for(int k = 1 ; k &lt; this-&gt;Nv+1 ; k++){	//k代表中间顶点 
			for(int i = 1  ; i &lt; this-&gt;Nv+1 ; i++){//i代表起始顶点 
				for(int j = 1 ; j &lt; this-&gt;Nv+1 ; j++){//j代表终点 
					if(this-&gt;dist[i][k] + this-&gt;dist[k][j] &lt; this-&gt;dist[i][j]){
						this-&gt;dist[i][j] = this-&gt;dist[i][k] + this-&gt;dist[k][j];
						if(i == j &amp;&amp; this-&gt;dist[i][j] &lt; 0){//发现了负值圈 
							return false;
						}
						this-&gt;path[i][j] = k;
					}					
				}
			}
		}
		return true; 
	}
	
	// 分治法寻找start到end最短路径的中间结点 
	void Find(queue&lt;int&gt; &amp;q ,int start,int end){
		int mid = this-&gt;path[start][end];
		if(mid == -1){
			return;
		}
		Find(q,start,mid);
		q.push(mid);
		Find(q,mid,end);
	}

	//打印start顶点到end顶点的路径 
	void Print_Path(int start,int end){
		queue&lt;int&gt; queue;
		queue.push(start);
		this-&gt;Find(queue,start,end); 
		queue.push(end);
		cout&lt;&lt;queue.front();
		queue.pop();
		while(!queue.empty()){
			cout&lt;&lt;"-&gt;"&lt;&lt;queue.front();
			queue.pop();
		}
		cout&lt;&lt;endl;
	}
	
	void Print_Floyd(){
		int i,j,k;
		for(int i = 1 ; i &lt; this-&gt;Nv+1 ; i++){
			for(int j = 1 ; j &lt; this-&gt;Nv+1 ; j++){
				cout&lt;&lt;this-&gt;path[i][j]&lt;&lt;" ";
			}
			cout&lt;&lt;endl;
		} 
		cout&lt;&lt;"	length		path"&lt;&lt;endl; 
		for(i = 1 ; i &lt; this-&gt;Nv+1 ; i++){
			for(j = i+1 ; j &lt; this-&gt;Nv+1 ; j++){
				cout&lt;&lt;i&lt;&lt;"-&gt;"&lt;&lt;j&lt;&lt;"	";
				cout&lt;&lt;this-&gt;dist[i][j]&lt;&lt;"		"; 	
				this-&gt;Print_Path(i,j);
			}
			cout&lt;&lt;endl;
		}
	}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62

};

int main()
{
cout<<“请输入顶点数与边长数:”<<endl;
int nv,ne;
cin>>nv>>ne;
Graph graph(nv,ne);
if(graph.Floyd()){
cout<<“各个顶点的最短路径为:”<<endl;
graph.Print_Floyd();
}

return 0;
  • 1

}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117

截图如下:
这里写图片描述

                                </div>
            <link href="https://csdnimg.cn/release/phoenix/mdeditor/markdown_views-e9f16cbbc2.css" rel="stylesheet">
                </div>
  • 1
  • 2
  • 3
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/人工智能uu/article/detail/734570
推荐阅读
相关标签
  

闽ICP备14008679号