最短路径
在网图和非网图中，最短路径的含义是不同的。由于非网图没有边上的权值，所谓的最短路径其实是指两顶点之间经过的边数最少的路径；而对于网图来说，最短路径指的是两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点。一般有两种最短路径。
第一种：从某个源点到其余各顶点的最短路径问题：Dijistra算法：
1.初始化：先找出从源点v0到各终点vk的直达路径(v0,vk),即通过一条弧到达的路径；
2.选择：从这些路径中找出一条长度最短的路径(v0,u)；
3.更新：然后对其余各条路径进行适当调整：
若在图中存在弧(u,vk)，且(v0,u)+(u,vk)<(v0,vk),则以路径(v0,u,vk)代替(v0,vk)。在调整后的各条路径中，再找长度最短的路径，依次类推。
即按照路径长度递增次序产生最短路径，具体来说：
1.把V分成两组
（1）S：已求出最短路径的顶点的集合；
（2）T=V-S:尚未确定最短路径的顶点集合。
2.将T中顶点按最短路径递增的次序加入到S中
保证：
（1）从源点v0到S中各顶点的最短路径都不大于从v0到T中任何顶点的最短路径长度。
（2）每个顶点对应一个距离值：
S中顶点：从v0到此顶点的最短路径长度。
T中顶点：从v0到此顶点的只包括S中顶点作中间顶点的最短路径长度。
第二种：求所有顶点间的最短路径
方法1：每次以一个顶点为源点，重复执行Dijkstra算法n次
方法2：弗洛伊德（Floyd）算法
思想：逐个顶点试探，从vi到vj的所有可能存在的路径中，选出一条长度最短的路径。
代码示例
关于图的邻接矩阵结构创建可查看以前的文章https://www.jianshu.com/p/b50ba1b3c327
MGraph.h
//Dijkstra算法（求有向网G的v0顶点到其余顶点v最短路径P[v]及带权长度D[v]）
typedef int Patharc[MAXVEX]; //存储最短路径下标的数组
typedef int ShortPathTable[MAXVEX]; //存储到各点最短路径的权值之和
//P[v]的值为前驱结点下标，D[v]表示v0到v的最短路径长度之和
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc P, ShortPathTable D);
//弗洛伊德（Floyd）算法，求网图G中各顶点v到其余顶点w最短路径P[v][w]及带权长度D[v][w]
typedef int Pathmatrix[MAXVEX][MAXVEX];
typedef int ShortPathTable_floyd[MAXVEX][MAXVEX];
void ShortestPath_Floyd(MGraph G, Pathmatrix P, ShortPathTable_floyd D);
MGraph.cpp
//P[v]的值为前驱结点下标，D[v]表示v0到v的最短路径长度之和
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc P, ShortPathTable D)
{
//step1:初始化
int final[MAXVEX] = { 0 }; //final[w]=1标志求得顶点v0->v1的最短路径，初始化为未知最短路径
for (int v = 0; v < G.numVertexes; v++)
{
P[v] = 0; //初始化路径数组为0
D[v] = G.arc[v0][v]; //初始化v0点与其他顶点之间的路径
}
D[v0] = 0; //v0与v0之间的路径为0
final[v0] = 1; //v0至v0不需要求路径
int min, k;
//step2:开始主循环,更新每个顶点距离v0的距离
for (int i = 1; i < G.numVertexes; i++)
{
min = MAXEDGE; //当前距离v0顶点的最近距离
for (int w = 0; w < G.numVertexes; w++)
{
if (!final[w] && D[w] < min) //到w顶点的最短路径还未求得，当前状态距离顶点k最近
{
k = w;
min = D[w];
}
}
final[k] = 1; //距离顶点k的最近距离已经找到
for (int w = 0; w < G.numVertexes; w++) //更新最短路径及距离
{
if (!final[w] && (G.arc[k][w] + min) < D[w]) //如果找到了更短路径，且顶点k可以到达w顶点
{
D[w] = min + G.arc[k][w]; //更新v0到w顶点的距离
P[w] = k; //v0到w的顶点的中间顶点为k，即更新v0顶点到w顶点的路径经过k
}
}
}
}
//floyd算法
void ShortestPath_Floyd(MGraph G, Pathmatrix P, ShortPathTable_floyd D)
{
//step1:初始化P、D
for (int i = 0; i < G.numVertexes; i++)
{
for (int j = 0; j < G.numVertexes; j++)
{
D[i][j] = G.arc[i][j];
P[i][j] = j;
}
}
//step2:更新P、D
for (int i = 0; i < G.numVertexes; i++) //每一个中转顶点加入后更新
{
for (int j = 0; j < G.numVertexes; j++) //更新P、D
{
for (int k = 0; k < G.numVertexes; k++)
{
if (D[j][k] > D[j][i] + D[i][k]) //如果该顶点j到k的路径经过i中转后变小，则进行更新
{
D[j][k] = D[j][i] + D[i][k];
P[j][k] = P[j][i]; //记录j到k经过顶点i中转
}
}
}
}
}
main.cpp
#include <iostream>
#include "MGraph.h"
#include "ALGraph.h"
#include <stack>
using namespace std;
extern bool* visited, * visited1;
int main(int argc, char** argv)
{
//1.邻接矩阵
MGraph MG;
CreateMGrah(MG);
for (int i = 0; i < MG.numVertexes; i++) //对于连通图，只执行一次
{
if (!visited[i])
{
DFS(MG, i); //深度优先搜索遍历
//BFS(MG, 0); //广度优先搜索遍历
}
}
cout << "\nPrim 最小生成树：" << endl;
/*
A D 1
A E 3
A B 7
B C 5
B E 2
C D 6
C E 8
D E 4
*/
MiniSpanTree_Prim(MG);
cout << "\nKruskal 最小生成树：" << endl;
//Edge edges[MAXEDGE] = { 0 };
//MGraph2Edge(MG, edges);
MiniSpanTree_Kruskal(MG);
cout << "\nDijkstra算法求解最短路径：" << endl;
Patharc P;
ShortPathTable D;
ShortestPath_Dijkstra(MG, 0, P, D);
for (int i = 1; i < MG.numVertexes; i++)
{
//输出v0到每一个顶点的最短路径
int p = P[i]; //到第i个顶点的倒数第二个顶点
stack<int> s;
while (p) //寻找中间顶点
{
s.push(p);
p = P[p]; //下一个顶点
}
//输出路径
cout << MG.vexs[0] << "->";
while (!s.empty())
{
cout << MG.vexs[s.top()] << "->";
s.pop();
}
cout << MG.vexs[i] << " " << D[i] << endl;
}
cout << "\nFloyd算法求解最短路径：" << endl;
Pathmatrix P_floyd;
ShortPathTable_floyd D_floyd;
ShortestPath_Floyd(MG, P_floyd, D_floyd);
//输出每一个顶点与其他顶点之间的最短路径
for (int i = 0; i < MG.numVertexes - 1; i++) //i为起点
{
for (int j = i + 1; j < MG.numVertexes; j++) //j为终点
{
cout << MG.vexs[i] << "->"; //输出源点
int k = P_floyd[i][j]; //中间顶点k
while (k != j) //直到终点
{
cout << MG.vexs[k] << "->";
k = P_floyd[k][j]; //继续找中间顶点
}
cout << MG.vexs[j]; //输出终点
cout << " " << D_floyd[i][j] << endl;
}
}
return 0;
}
网友评论