最短路径-Dijkstra算法与Floyd算法

最短路径-Dijkstra算法与Floyd算法

原文：https://www.cnblogs.com/smile233/p/8303673.html

一、最短路径

　　①在非网图中，最短路径是指两顶点之间经历的边数最少的路径。

AE：1    ADE：2   ADCE：3   ABCE：3

　　②在网图中，最短路径是指两顶点之间经历的边上权值之和最短的路径。 

AE：100   ADE：90   ADCE：60   ABCE：70

　　③单源点最短路径问题

　　问题描述：给定带权有向图G＝(V, E)和源点v∈V，求从v到G中其余各顶点的最短路径。

　　应用实例——计算机网络传输的问题：怎样找到一种最经济的方式，从一台计算机向网上所有其它计算机发送一条消息。

　　④每一对顶点之间的最短路径

　　问题描述：给定带权有向图G＝(V, E)，对任意顶点vi,vj∈V（i≠j），求顶点vi到顶点vj的最短路径。

　　解决办法1：每次以一个顶点为源点，调用Dijkstra算法n次。显然，时间复杂度为O(n3)。 解决办法2：弗洛伊德提出的求每一对顶点之间的最短路径算法——Floyd算法，其时间复杂度也是O(n3)，但形式上要简单些。

二、Dijkstra算法

　　①基本思想：设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对vi∈V-S，假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v, …, vk，就将vk加入集合S中，并将路径v, …, vk , vi与原来的假设相比较，取路径长度较小者为最短路径。重复上述过程，直到集合V中全部顶点加入到集合S中。

　　②设计数据结构 :

　　1、图的存储结构：带权的邻接矩阵存储结构 。

　　2、数组dist[n]：每个分量dist[i]表示当前所找到的从始点v到终点vi的最短路径的长度。初态为：若从v到vi有弧，则dist[i]为弧上权值；否则置dist[i]为∞。

　　3、数组path[n]：path[i]是一个字符串，表示当前所找到的从始点v到终点vi的最短路径。初态为：若从v到vi有弧，则path[i]为vvi；否则置path[i]空串。

　　4、数组s[n]：存放源点和已经生成的终点，其初态为只有一个源点v。

　　③Dijkstra算法——伪代码

      1 1. 初始化数组dist、path和s；
      2 2. while (s中的元素个数<n)
      3 2.1 在dist[n]中求最小值，其下标为k；
      4 2.2 输出dist[j]和path[j]；
      5 2.3 修改数组dist和path；
      6 2.4 将顶点vk添加到数组s中；
  
 

 　　④C++代码实现

       1 #include<iostream>
       2 #include<fstream>
       3 #include<string>
       4 using  namespace std;
       5 #define MaxSize  10
       6 #define MAXCOST 10000
       7 // 图的结构
       8 template<class T>
       9 struct Graph
      10 {
      11 T vertex[MaxSize];// 存放图中顶点的数组
      12 int arc[MaxSize][MaxSize];// 存放图中边的数组
      13 int vertexNum, arcNum;// 图中顶点数和边数
      14 };
      15 // 最短路径Dijkstra算法
      16 void Dijkstra(Graph<string> G,int v)
      17 {
      18 int dist[MaxSize];//  i到j的路径长度
      19 string path[MaxSize];// 路径的串
      20 int s[MaxSize];// 已找到最短路径的点的集合
      21 bool Final[MaxSize];//Final[w]=1表示求得顶点V0至Vw的最短路径
      22 // 初始化dist\path
      23 for (int i = 0; i < G.vertexNum; i++)
      24 {
      25 Final[i] = false;
      26 dist[i] = G.arc[v][i];
      27 if (dist[i] != MAXCOST)
      28 path[i] = G.vertex[v] + G.vertex[i];
      29 else
      30 path[i] = " ";
      31 }
      32 s[0] = v; // 初始化s
      33 Final[v] = true;
      34 int num = 1;
      35 while (num < G.vertexNum)
      36 {
      37 // 在dist中查找最小值元素
      38 int k = 0,min= MAXCOST;
      39 for (int i = 0; i < G.vertexNum; i++)
      40 {
      41 if (i == v)continue;
      42 if (!Final[i] && dist[i] < min)
      43 {
      44 k = i;
      45 min = dist[i];
      46 }
      47 }
      48 cout << dist[k]<<path[k]<<endl;
      49 s[num++] = k;// 将新生成的结点加入集合s
      50 Final[k] = true;
      51 // 修改dist和path数组
      52 for (int i = 0; i < G.vertexNum; i++)
      53 {
      54 if (!Final[i]&&dist[i] > dist[k] + G.arc[k][i])
      55 {
      56 dist[i] = dist[k] + G.arc[k][i];
      57 path[i] = path[k] + G.vertex[i];
      58 }
      59 }
      60 }
      61 }
      62 int main()
      63 {
      64 // 新建图
      65 Graph<string> G;
      66 string temp[]= { "v0","v1","v2","v3","v4" };
      67 /*int length = sizeof(temp) / sizeof(temp[0]);
      68 G.vertexNum = length;
      69 G.arcNum = 7;*/
      70 ifstream in("input.txt");
      71 in >> G.vertexNum >> G.arcNum;
      72 // 初始化图的顶点信息
      73 for (int i = 0; i < G.vertexNum; i++)
      74 {
      75 G.vertex[i] = temp[i];
      76 }
      77 //初始化图G的边权值
      78 for (int i =0; i <G.vertexNum; i++)
      79 {
      80 for (int j = 0; j <G.vertexNum; j++)
      81 {
      82 G.arc[i][j] = MAXCOST;
      83 }
      84 }
      85 for (int i = 0; i < G.arcNum; i++)
      86 {
      87 int m, n,cost;
      88 in >> m >> n >> cost;
      89 G.arc[m][n] = cost;
      90 }
      91 Dijkstra(G, 0);
      92 system("pause");
      93 return 0;
      94 }
  
 

      // input.txt
      1 5 7
      2 0 1 10
      3 0 3 30
      4 0 4 100
      5 1 2 50
      6 2 4 10
      7 3 2 20
      8 3 4 60
  
 

三、Floyd算法

　　①基本思想：对于从vi到vj的弧，进行n次试探：首先考虑路径vi,v0,vj是否存在，如果存在，则比较vi,vj和vi,v0,vj的路径长度，取较短者为从vi到vj的中间顶点的序号不大于0的最短路径。在路径上再增加一个顶点v1，依此类推，在经过n次比较后，最后求得的必是从顶点vi到顶点vj的最短路径。

　　②设计数据结构

　　1、图的存储结构：带权的邻接矩阵存储结构  。

　　2、数组dist[n][n]：存放在迭代过程中求得的最短路径长度。迭代公式：

　　3、数组path[n][n]：存放从vi到vj的最短路径，初始为path[i][j]="vivj"。

　　③C++代码实现

       1 #include<iostream>
       2 #include<fstream>
       3 #include<string>
       4 using  namespace std;
       5 #define MaxSize  10
       6 #define MAXCOST 10000
       7 int dist[MaxSize][MaxSize];// 存放在迭代过程中求得的最短路径
       8 string path[MaxSize][MaxSize];// vi到vj的最短路径
       9 // 图的结构
      10 template<class T>
      11 struct Graph
      12 {
      13 T vertex[MaxSize];// 存放图中顶点的数组
      14 int arc[MaxSize][MaxSize];// 存放图中边的数组
      15 int vertexNum, arcNum;// 图中顶点数和边数
      16 };
      17 void Floyd(Graph<string> G)
      18 {
      19 // 初始化
      20 for(int i=0;i<G.vertexNum;i++)
      21 for (int j = 0; j < G.vertexNum; j++)
      22 {
      23 if (i == j) { dist[i][j] = 0; path[i][j] = ""; }
      24 dist[i][j] = G.arc[i][j];
      25 if (dist[i][j] != MAXCOST)
      26 path[i][j] = G.vertex[i] + G.vertex[j];
      27 else
      28 path[i][j] = " ";
      29 }
      30 // 进行n次迭代
      31 for(int k=0;k<G.vertexNum;k++)
      32 for(int i=0;i<G.vertexNum;i++)
      33 for (int j = 0; j < G.vertexNum; j++)
      34 if (dist[i][k] + dist[k][j] < dist[i][j])
      35 {
      36 dist[i][j] = dist[i][k] + dist[k][j];
      37 path[i][j] = path[i][k] + path[k][j];
      38 }
      39 }
      40 int main()
      41 {
      42 int i, j, cost;
      43 Graph<string> G;// 存放图的信息
      44 ifstream in("input.txt");
      45 in >> G.vertexNum >> G.arcNum;
      46 string temp[] = { "a","b","c" };
      47 // 初始化图的顶点信息
      48 for (int i = 0; i < G.vertexNum; i++)
      49 {
      50 G.vertex[i] = temp[i];
      51 }
      52 //初始化图G
      53 for (i = 0; i < G.vertexNum; i++)
      54 {
      55 for (j = 0; j < G.vertexNum; j++)
      56 {
      57 G.arc[i][j] = MAXCOST;
      58 }
      59 }
      60 //构建图G
      61 for (int k = 0; k <G.arcNum; k++)
      62 {
      63 in >> i >> j >> cost;
      64 G.arc[i][j] = cost;
      65 }
      66 Floyd(G);
      67 for (i = 0; i < G.vertexNum; i++)
      68 {
      69 for (j = 0; j < G.vertexNum; j++)
      70 {
      71 if (i != j)
      72 {
      73 cout << "顶点" << i << "到顶点" << j << "的最短路径长度为" << dist[i][j] << endl;
      74 cout << "具体路径为:" << path[i][j] << endl;
      75 }
      76 }
      77 }
      78 system("pause");
      79 return 0;
      80 }
  
 

      // input.txt
      3 5
      0 1 4
      1 0 6
      0 2 11
      2 0 3
      1 2 2
  
 

文章来源: blog.csdn.net，作者：网奇，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/jacke121/article/details/88779302