别说了 世界那么大我想去看看！（最短路径-迪杰斯特拉算法弗洛伊德算法）

前言：

一直想去外面的世界看看，中国城市那么多，那么美，怎么样才可以用最少的钱，最短的时间游遍我想去的城市呢？（我在做梦？不不不！迪杰斯特拉算法和弗洛伊德算法来了）

这两个算法有着广泛的用途，让我们来康康：

（***后附代码演示哦！！！***）

多么厉害的应用啊，那么让我们来一起学习吧！

一、迪杰斯特拉算法（Dijkstra）

首先说说迪杰斯特拉算法的求解过程：

对于网N=（V，E），将N中的顶点分成两组：第一组 S：已求出的最短路径的终点集合（初始时只包含源点v0）第二组V-S：尚未求出的最短路径的顶点集合（初始时为V-{v0}）算法将按各顶点与v0间最短路径长度递增的次序，逐个将集合V-S中的顶点加入到集合S中去。在这个过程中，总保持v0到集合S中各顶点的路径长度始终不大于到集合V-S中各顶点的路径长度。

总结归纳：首先我们知道，这点很重要！

在这条路径上，必定只含一条边，并且这条边是所有从源点v0出发的所有边中权值最小的一条。那么你想，到其它边最小的，肯定要经过之前最小的邻接边，所以核心思想我们可以说成是依各条最短路径的长度递增的次序依次求得各条路径。

下一条路径长度次短的最短路径的特点:（假设其终点为vk）它只可能有两种情况:

或者是直接从源点到该顶点的边: <v0vk> (只含一条边)；

或者是，从源点经过顶点u，再到达该顶点的两条边组成: <v0 u> < u vk>。 依次类推：一般情况下,下一条最短路径的特点： 它或者是直接从源点直达该顶点的一条弧；

或者是，从源点经过已求得了最短路径的顶点集合中的顶点，再到达该顶点。

算法步骤：

这里需要知道存储结构一点知识有： 邻接矩阵G[n][n] (或者邻接表) 辅助数组： 数组S[n]： 记录相应顶点是否已求出最短路径

数组D[n]： 记录当前所求出的从源点到相应顶点的最短路径长度 数组Path[n]： 记录相应顶点路径中的前驱顶点

(1)初始化：

将源点v0加到S中，即S[v0]=true;将v0到各个终点的最短路径长度初始化为权值，即D[i]=G.arcs[v0][vi]，(vi∈V-S);如果v0和顶点vi之间有弧，则将vi的前驱置为v0，即Path[i]=v0，否则Path[i]=-1。

（2）循环n-1次，执行以下操作：选择下一条最短路径的终点vk，使得：

D[k]=Min{D[i]|vi∈V-S}将vk加到S中，即S[k]=true;根据条件更新从v0出发到集合V-S上任一顶点的最短路径的长度，若条件D[k]+G.arcs[k][i]<D[i]成立，则更新D[i]=D[k]+G.arcs[k][i]，同时更改vi的前驱为vk；Path[i]=k。

为了更好的理解，将上面的总结就是：

1.初始化：先找出从源点v0到各终点vk的直达路径（v0,vk），即通过一条弧到达的路径。

2.选择：从这些路径中找出一条长度最短的路径（v0,u）。

3.更新：然后对其余各条路径进行适当调整：

判断：若在图中存在弧（u,vk），且（v0,u）+（u,vk）<（v0,vk）,

则以路径（v0,u,vk）代替（v0,vk）。

在调整后的各条路径中，再找长度最短的路径，

依此类推。

看这个例子更好的理解：

求这个图的最短路径就有：

二、弗洛伊德算法

迪杰斯特拉是从一个点到其余各点的最短路径，二弗洛伊德则是每对顶点之间的最短路径。这个时候聪明的你是不是想到调用迪杰斯特拉算法呢？一起来看看趴

弗洛伊德算法的基本思想是：

从 vi 到 vj 的所有可能存在的路径中，选出一条长度最短的路径

算法：

若<vi,vj>存在，则存在路径{vi,vj}

// 路径中不含其它顶点

若<vi,v1>,<v1,vj>存在，则存在路径{vi,v1,vj}

// 路径中所含顶点序号不大于1

若{vi,…,v2}, {v2,…,vj}存在，

则存在一条路径{vi, …, v2, …vj}

// 路径中所含顶点序号不大于2

…

依次类推，则 vi 至 vj 的最短路径应是上述这些路径中，路径长度最小者。

****下面演示代码：

迪杰斯特拉算法：

//算法 迪杰斯特拉算法#include <iostream>using namespace std;#define MaxInt 32767//表示极大值，即∞#define MVNum 100 //最大顶点数typedef char VerTexType; //假设顶点的数据类型为字符型typedef int ArcType; //假设边的权值类型为整型int *D=new int[MVNum];//用于记录最短路的长度bool *S=new bool[MVNum];//标记顶点是否进入S集合int *Path=new int[MVNum];//用于记录最短路顶点的前驱//------------图的邻接矩阵-----------------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;}//LocateVexvoid CreateUDN(AMGraph &G){//采用邻接矩阵表示法，创建无向网Gint i , j , k;cout <<"请输入总顶点数，总边数，以空格隔开:";cin >> G.vexnum >> G.arcnum;//输入总顶点数，总边数cout << endl;cout << "输入点的名称:，如a" << endl;for(i = 0; i < G.vexnum; ++i){cout << "请输入第" << (i+1) << "个点的名称:";cin >> G.vexs[i]; //依次输入点的信息}cout << endl;for(i = 0; i < G.vexnum; ++i)//初始化邻接矩阵，边的权值均置为极大值MaxIntfor(j = 0; j < G.vexnum; ++j)G.arcs[i][j] = MaxInt;cout << "输入边依附的顶点及权值，如a b 7" << endl;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>的权值置为wG.arcs[j][i] = G.arcs[i][j];//置<v1, v2>的对称边<v2, v1>的权值为w}//for}//CreateUDNvoid ShortestPath_DIJ(AMGraph G, int v0){//用Dijkstra算法求有向网G的v0顶点到其余顶点的最短路径int v , i , w , min;int n = G.vexnum;//n为G中顶点的个数for(v = 0; v < n; ++v){//n个顶点依次初始化S[v] = false; //S初始为空集D[v] = G.arcs[v0][v]; //将v0到各个终点的最短路径长度初始化为弧上的权值if(D[v] < MaxInt) Path [v] = v0; //如果v0和v之间有弧，则将v的前驱置为v0else Path [v] = -1;//如果v0和v之间无弧，则将v的前驱置为-1}//forS[v0]=true;//将v0加入SD[v0]=0; //源点到源点的距离为0/*―初始化结束，开始主循环，每次求得v0到某个顶点v的最短路径，将v加到S集―*/for(i = 1;i < n; ++i){//对其余n-1个顶点，依次进行计算min= MaxInt;for(w = 0; w < n; ++w)if(!S[w] && D[w] < min){//选择一条当前的最短路径，终点为vv = w;min = D[w];}//ifS[v]=true; //将v加入Sfor(w = 0;w < n; ++w) //更新从v0出发到集合V?S上所有顶点的最短路径长度if(!S[w] && (D[v] + G.arcs[v][w] < D[w])){D[w] = D[v] + G.arcs[v][w]; //更新D[w]Path [w] = v; //更改w的前驱为v}//if}//for}//ShortestPath_DIJvoid DisplayPath(AMGraph G , int begin ,int temp ){//显示最短路if(Path[temp] != -1){DisplayPath(G , begin ,Path[temp]);cout << G.vexs[Path[temp]] << "-->";}}//DisplayPathint main(){cout << "************迪杰斯特拉算法**************" << endl << endl;AMGraph G;int i , j ,num_start , num_destination;VerTexType start , destination;CreateUDN(G);cout <<endl;cout << "*****无向网G创建完成！*****" << endl;for(i = 0 ; i < G.vexnum ; ++i){for(j = 0; j < G.vexnum; ++j){if(j != G.vexnum - 1){if(G.arcs[i][j] != MaxInt)cout << G.arcs[i][j] << "\t";elsecout << "∞" << "\t";}else{if(G.arcs[i][j] != MaxInt)cout << G.arcs[i][j] <<endl;elsecout << "∞" <<endl;}}}//forcout << endl;cout << "请依次输入起始点、终点名称：";cin >> start >> destination;num_start = LocateVex(G , start);num_destination = LocateVex(G , destination);ShortestPath_DIJ(G , num_start);cout << endl <<"最短路径为：";DisplayPath(G , num_start , num_destination);cout << G.vexs[num_destination]<<endl;return 0;}//main

演示例子的话可以用上图哦。

弗洛伊德算法：

//算法 弗洛伊德算法#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;}//LocateVexvoid CreateUDN(AMGraph &G){//采用邻接矩阵表示法，创建有向网Gint i , j , k;cout <<"请输入总顶点数，总边数，以空格隔开:";cin >> G.vexnum >> G.arcnum;//输入总顶点数，总边数cout << endl;cout << "输入点的名称，如a" << endl;for(i = 0; i < G.vexnum; ++i){cout << "请输入第" << (i+1) << "个点的名称:";cin >> G.vexs[i]; //依次输入点的信息}cout << endl;for(i = 0; i < G.vexnum; ++i){//初始化邻接矩阵，边的权值均置为极大值MaxIntfor(j = 0; j < G.vexnum; ++j){if(j != i)G.arcs[i][j] = MaxInt;elseG.arcs[i][j] = 0;}//for}//forcout << "输入边依附的顶点及权值，如a b 3" << endl;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}//CreateUDNvoid ShortestPath_Floyed(AMGraph G){//用Floyd算法求有向网G中各对顶点i和j之间的最短路径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];if(D[i][j] < MaxInt && i != j) Path[i][j]=i; //如果i和j之间有弧，则将j的前驱置为ielse Path [i][j] = -1; //如果i和j之间无弧，则将j的前驱置为-1}//forfor(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]){//从i经k到j的一条路径更短D[i][j] = D[i][k]+D[k][j]; //更新D[i][j]Path[i][j] = Path[k][j]; //更改j的前驱为k}//if}//ShortestPath_Floyedvoid DisplayPath(AMGraph G , int begin ,int temp ){//显示最短路径if(Path[begin][temp] != -1){DisplayPath(G , begin ,Path[begin][temp]);cout << G.vexs[Path[begin][temp]] << "-->";}}//DisplayPathint main(){cout << "************弗洛伊德算法**************" << endl << endl;AMGraph G;char start , destination;int num_start , num_destination;CreateUDN(G);cout <<endl;cout << "有向网G创建完成！" << endl;ShortestPath_Floyed(G);cout << "请依次输入路径的起点与终点的名称：";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;cout <<endl;return 0;}//main

后记：

这里我着重迪杰斯特拉算法，因为弗洛伊德其实本质也是一样的，如果需要了解更多可以去查阅其它资料哦。

ps别拦着我，我要去看世界了…竟然没钱！！哭了，看来巧妇难为无米之炊啊。那么我要去搬砖赚钱啦，期待下一篇博客，冲鸭，搬砖去啦！