当前位置：个人在线分享 > 【数据结构】图论中求最短路径——迪杰斯特拉算法（Dijkstra）、弗洛伊德算法（Floyd）
  • 文章介绍

    • 有疑问？请点击复制链接咨询！

    目录

    • 最短路径 (*)
      • 迪杰斯特拉算法（Dijkstra）
        • 迪杰斯特拉算法（Dijkstra）的算法原理：
      • 弗洛伊德算法（Floyd）
        • 弗洛伊德算法（Floyd）的算法原理：
        • 弗洛伊德算法的（c语言）完整实例：

    最短路径 (*)

    生活中最短路径问题例如：
    交通网络：给定了该网内的n个城市以及这些市之间的相通公路的距离，能否找到城市A城市B之间一条最近的通路呢？

    1. 从A地到B地换车次数最少的路径
    2. 从A地到B地最短的路径（距离最短，行驶时间最短，费用最低）
    1. 迪杰斯特拉(Dijkstra)算法–从一个源点到其它各点的最短路径
    2. 弗洛伊德(Floyd)算法–每一对顶点之间的最短路径
    3. 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中、或源点到剩余顶点的路径都是∞为止。

    【数据结构】图论中求最短路径——迪杰斯特拉算法（Dijkstra）、弗洛伊德算法（Floyd）插图

    一、图的存储：邻接矩阵和邻接表都可以

    #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）

    【数据结构】图论中求最短路径——迪杰斯特拉算法（Dijkstra）、弗洛伊德算法（Floyd）插图(1)

    图的存储：邻接矩阵和邻接表都可以

    #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  
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;                                                                //边的权值置为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("
G.arc矩阵的结果如下：
");
// for( i=0;i<G.vexnum;i++ )     // 输出
// {
// 	for( j=0;j<G.vexnum;j++ )
// 	{
// 		printf("%d  ",G.arcs[i][j]);
// 	}
// 	printf("
");
// }
// 	printf("
距离矩阵的结果如下：
");
// for( i=0;i<G.vexnum;i++ )     // 输出
// {
// 	for( j=0;j<G.vexnum;j++ )
// 	{
// 		printf("%d  ",D[i][j]);
// 	}
// 	printf("
");
// }
// printf("
路径矩阵的结果如下：
");
// for( i=0;i<G.vexnum;i++ )     // 输出
// {
// 	for( j=0;j<G.vexnum;j++ )
// 	{
// 		printf("%d  ",Path[i][j]);
// 	}
// 	printf("
");
// }
}
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
    本站无任何商业行为
    个人在线分享 » 【数据结构】图论中求最短路径——迪杰斯特拉算法（Dijkstra）、弗洛伊德算法（Floyd）
    admin

    admin 钻石

    分享到：

    相关推荐

    E-->