【数据结构】图论中求最短路径——迪杰斯特拉算法（Dijkstra）、弗洛伊德算法（Floyd）
数据结构——图论中求最短路径——迪杰斯特拉算法（Dijkstra）、弗洛伊德算法（Floyd）
目录
最短路径 (*)
生活中最短路径问题例如：
交通网络：给定了该网内的n个城市以及这些市之间的相通公路的距离，能否找到城市A城市B之间一条最近的通路呢？
- 从A地到B地换车次数最少的路径
- 从A地到B地最短的路径（距离最短，行驶时间最短，费用最低）
- 迪杰斯特拉(Dijkstra)算法–从一个源点到其它各点的最短路径
- 弗洛伊德(Floyd)算法–每一对顶点之间的最短路径
- Bellman-Ford算法
迪杰斯特拉算法（Dijkstra）
该算法只适用于静态网络网络上边的权值不能为负数
基本思想：设集合S中存放已找到最短路径的顶点，集合
T
＝
V
−
S
T ＝V-S
T＝V−S存放当前还未找到最短路径的顶点。
1.初态: S中 只包含源点 v0，v0到其余 各点的弧 为各点当前各点的“最短”路径。
2.从T中选取当前各点的“最短”路径长度中最短的顶点u加入到S中。
3.S加入新的顶点u后，考察顶点
v
0
v_0
v0到T中剩余顶点的最短路径长度是否可以优化更新：T中各顶点新的最短路径长度值为原来的最短路径长度值、顶点u的最短路径长度值加上u到该顶点的路径长度值中的较小值。
4.重复2，3，直到T的顶点全部加入到S中、或源点到剩余顶点的路径都是∞为止。
一、图的存储：邻接矩阵和邻接表都可以
#define max 100
typedef struct {
int arcs[max][max];
int vexnum,arcnum;
}AGraphs;
Agraphs G；//定义图存储结构 邻接矩阵的存储形式
二、区分已经求出最短路径的点
方法一:设一个一维数组int final[max];
final[i]=1表示从源点到顶点i的最短路径已经求出，i在S中
final[i]=0表示从源点到顶点i的最短路径尚未求出，i在V-S中
方法二：利用邻接矩阵主对角线的位置G.arcs[i][i]表示i是否在S中
G.arcs[i][i]=1表示从源点到顶点i的最短路径已经求出，i在S中
G.arcs[i][i]=0表示从源点到顶点i的最短路径尚未求出，i在V-S中
三、表示源点到顶点i的最短路径
一维数组int D[max]表示最短路径的长度
D[i] ：从源点到点
v
i
v_i
vi的最短路径的长度
初态为：若从源点 到
v
i
v_i
vi有弧，则D[i]为弧上的权值；否则置 D[i]为∞ ，即：D[i]=G.arcs[k][i]; //说明：k为源点
二维数组int P[max][max]表示最短路径包含的顶点
P[i][ ] ：从源点到点
v
i
v_i
vi的最短路径
P[i][j]=0 ：
v
j
v_j
vj不在从源点 到点
v
i
v_i
vi的最短路径上
P[i][j]=1 ：
v
j
v_j
vj位于从源点 到点
v
i
v_i
vi的最短路径上。
迪杰斯特拉算法（Dijkstra）的算法原理：
void ShortestPath(AGraphs G,int k,int P[][], int D[]){
int i,w, j,min;
for (i=0;i<G.vexnum; i ++){
final[i]=0; //初始化
D[i]=G.arcs[k][i];//最短路径长度
for(w=0;w<G.vexnum; w ++)
P[i][w]=0;//初始化
if (D[i]<INFINITY){ //短路径包含的顶点
P[i][k]=1;
P[i][i]=1;
}
}
D[k]=0; //初始点
final[k]=1;
for(i=1; i<G.vexnum; i ++){
min=INFINITY;//初始化为 无穷大
for (w=0;w<G.vexnum; w ++)
if (!final[w]&&D[w]<min){//
j=w;
min=D[w];
}
if(min== INFINITY) //
return;
final[j]=1; //标记为选入
for(w=0;w<G.vexnum; w ++)
if(!final[w]&&(min+G.arcs[j][w]<D[w])){
D[w]=min+G.arcs[j][w];
P[w]=P[j]; //？？
P[w][w]=1;
}
}
弗洛伊德算法（Floyd）
图的存储：邻接矩阵和邻接表都可以
#define max 100
typedef struct {
int arcs[max][max];
int vexnum,arcnum;
}AGraphs;
Agraphs G；//定义图存储结构 邻接矩阵的存储形式
弗洛伊德算法（Floyd）的算法原理：
void s1(int D[][],int p[][][], Agraphs G){
int i,j,k;
for(i=0;i<G. vexnum;i++)
for(j=0;j<G. vexnum;j++){
D[i][j]=G.arcs[i][j];
for(k=0;k<G.vnum;k++)
p[i][j][k]=0; //初始化
if(D[i][j]<INFINITY){
p[i][j][i]=1; //初始化
p[i][j][j]=1; //初始化
}
}
for (k=0;k<G. vexnum;k++)
for (i=0;i<G. vexnum;i++)
for(j=0;j<G vexnum;j++)
if(D[i][k]+D[k][j]<D[i][j]){//是否K 加入能够减小路径长度
D[i][j]=D[i][k]+D[k][j];//如果可以 就加入
for(w=0;w<G. vexnum;w++)
p[i][j][w]=p[i][k][w]||p[k][j][w];//然后确定路径上的元素
}
}
弗洛伊德算法的（c语言）完整实例：
//算法6.11 弗洛伊德算法
#include <iostream>
using namespace std;
#define MaxInt 32767 //表示极大值，即∞
#define MVNum 100 //最大顶点数
typedef char VerTexType; //假设顶点的数据类型为字符型
typedef int ArcType; //假设边的权值类型为整型
int Path[MVNum][MVNum]; //最短路径上顶点vj的前一顶点的序号
int D[MVNum][MVNum]; //记录顶点vi和vj之间的最短路径长度
//------------图的邻接矩阵---------------
typedef struct{
VerTexType vexs[MVNum]; //顶点表 ？
ArcType arcs[MVNum][MVNum];//邻接矩阵
int vexnum,arcnum; //图的当前点数和边数
}AMGraph;
int LocateVex(AMGraph G , VerTexType v){
//确定点v在G中的位置
for(int i = 0; i < G.vexnum; ++i)
if(G.vexs[i] == v)
return i;
return -1;
}//LocateVex
void CreateUDN(AMGraph &G){
//采用邻接矩阵表示法，创建有向网G
int i , j , k;
//cout <<"请输入总顶点数，总边数，以空格隔开:";
cin >> G.vexnum >> G.arcnum; //输入总顶点数，总边数
//cout << "输入点的名称，如a" << endl;
for(i = 0; i < G.vexnum; ++i){
//cout << "请输入第" << (i+1) << "个点的名称:";
cin >> G.vexs[i]; //依次输入点的信息
}
for(i = 0; i < G.vexnum; ++i){ //初始化邻接矩阵，边的权值均置为极大值MaxInt
for(j = 0; j < G.vexnum; ++j){
if(j != i)
G.arcs[i][j] = MaxInt;
else
G.arcs[i][j] = 0;
}//for
}//for //初始化
//cout << "输入边依附的顶点及权值，如a b 3" << end；
for(k = 0; k < G.arcnum;++k){ //构造邻接矩阵
VerTexType v1 , v2;
ArcType w;
//cout << "请输入第" << (k + 1) << "条边依附的顶点及权值:";
cin >> v1 >> v2 >> w; //输入一条边依附的顶点及权值
i = LocateVex(G, v1); j = LocateVex(G, v2); //确定v1和v2在G中的位置，即顶点数组的下标
G.arcs[i][j] = w; //边<v1, v2>的权值置为w
}//for
}//CreateUDN
/*
【样例输入】
4 5
A B C D
A B 2
A C 4
B C 3
B D 5
C D 1
A D
【样例输出】
5
*/
void ShortestPath_Floyed(AMGraph G){
int i, j, k;
for( i=0;i<G.vexnum;i++ )
{
for( j=0;j<G.vexnum;j++ )
{
D[i][j] = G.arcs[i][j]; // 距离矩阵初始化
Path[i][i] = i; // 路径矩阵初始化
if(G.arcs[i][j]!=MaxInt){
Path[i][j]=i;
}
}
}
for( k=0;k<G.vexnum;k++ )
{
for( i=0;i<G.vexnum;i++ )
{
for( j=0;j<G.vexnum;j++ )
{
if( D[i][k] + D[k][j] < D[i][j] )
{
D[i][j] = D[i][k] + D[k][j]; // 动态更新距离矩阵
Path[i][j] = Path[k][j]; // 动态更新路径矩阵
}
}
}
}
//test 看每个矩阵的结果
// printf("\nG.arc矩阵的结果如下：\n");
// for( i=0;i<G.vexnum;i++ ) // 输出
// {
// for( j=0;j<G.vexnum;j++ )
// {
// printf("%d ",G.arcs[i][j]);
// }
// printf("\n");
// }
// printf("\n距离矩阵的结果如下：\n");
// for( i=0;i<G.vexnum;i++ ) // 输出
// {
// for( j=0;j<G.vexnum;j++ )
// {
// printf("%d ",D[i][j]);
// }
// printf("\n");
// }
// printf("\n路径矩阵的结果如下：\n");
// for( i=0;i<G.vexnum;i++ ) // 输出
// {
// for( j=0;j<G.vexnum;j++ )
// {
// printf("%d ",Path[i][j]);
// }
// printf("\n");
// }
}
void DisplayPath(AMGraph G , int begin ,int temp ){
//显示最短路径
if(Path[begin][temp] != -1){
DisplayPath(G , begin ,Path[begin][temp]);
cout << G.vexs[Path[begin][temp]] << "-->";
}
}//DisplayPath
int main(){
//cout << "************算法6.11 弗洛伊德算法**************" << endl << endl;
AMGraph G;
char start , destination;
int num_start , num_destination;
CreateUDN(G);
//test
//cout << "有向网G创建完成！" << endl;
//test
//需要完成的函数
ShortestPath_Floyed(G);
//需要完成的函数
//test
//cout << "请依次输入路径的起点与终点的名称：";
//test
cin >> start >> destination;
num_start = LocateVex(G , start);
num_destination = LocateVex(G , destination);
//DisplayPath(G , num_start , num_destination);
//cout << G.vexs[num_destination] << endl;
cout << D[num_start][num_destination] << endl;
return 0;
}//main
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
17
0- 0
已为社区贡献6条内容
所有评论(0)