案例引入
日常生活中常常涉及最短路径问题，如在一个城市交通网中，如何选取从起点到达终点的路径，才能使这一趟旅程的路程最短？或所需时间最少？或所需交通费用最低？诸如此类问题都可以抽象为求解图的最短路径问题。我们把图的顶点表示为城市的交通站点，边表示交通站点间的路径，边的权值表示为交通站点间的路径的距离、所需时间或费用等等，则上述问题放映到图上就是，如何求解图顶点间权值之和最小的路径。
由于城市交通站点间具有方向性，故常选取带权值的有向网表示城市交通网。习惯上，在有向网的一条路径中，第一个顶点被称为源点，最后一个顶点被称为终点。
常见的最短路径问题分为两类：单源点到达其余顶点的最短路径以及任意一对顶点间的最短路径。
求解单源点到其余顶点的最短路径问题
迪杰斯特拉算法(DIJ)思路
常用于求解单源点到其余顶点的最短路径问题的DIJ算法主要采用了源点借助中转点能获取到达终点更短路径的方法，逐步将其余顶点加入最短路径终点集。
如图所示，A借助B作为中转点获得到达C的更短路径：
算法的求解过程
对于有向网N=(V,E)而言，欲求顶点v（
）到达N的其余顶点 V-{v}的最短路径,可以将N的顶点分为两部分S与V-S，S用于存放已经确定最短路径的终点，V-S用于存放没有确定为最短路径的顶点。每一次S获取新成员前都需要挑选权值最小的<v,t>,将t加入到S中，同时源点v将利用最新最短路径终点t作为中转点更新源点v到达其余在V-S中顶点的最短路径，直到S==V。
注意：假如出现两条最短路径相同的情况，则随意选取其中一条。
在上述过程中，我们可以保证每一次加入的最短路径终点u都是正确的，且后续加入的终点t无法被源点v借用以更新源点到终点u的更小路径权值。这是因为，假设dis(v,u)表示从顶点v到顶点u的权值，那么由于终点u比终点t提前进入最短路径终点集S，则dis(v,u)>=dis(v,t)，那么dis(v,t)+dis(t,u)>dis(v,u)必定无法成立。除非dis(t,u)<0,存在负权边，但这不在我们的考虑范围之内(城市中的距离或一段旅程的花销一般情况下不会出现现负值)。
数据结构说明
本例采取邻接矩阵作为有向网的存储结构，其中Vertype表示顶点的数据类型，ArcType表示边的权值，Mvnum表示邻接矩阵的最大顶点数目。在为邻接矩阵初始化过程中，假如两顶点间不存在路径，那么G.arcs[i][j]=inf(inf是一个较大数，表示无穷大)。
辅助数组说明
第一，我们需要bool S[Mvnum]用以记录网中顶点是否已经进入到最短路径终点集，且初始化为S[v]=true,其余顶点S[i]=false,此过程将在Init函数中进行。
第二，我们需要int shortestDis[Mvnum]用以记录当前源点到各个终点的最短路径。在初始化时，该数组shortestDis[i]表示源点到下标为i的顶点间的路径权值，初始化同样是在Init函数中进行。
第三，我们需要int Path[Mvnum]用于记录,在当前源点到各个顶点的最短路径<v,vi>上，顶点vi的直接前驱，方便获取最短路径上经历过的顶点顺序。在初始化时，假如<v,vi>存在路径，则Path[vi]=v,否则Path[vi]=-1.
算法的代码实现
AMGraph的实现
//文件名为：AMGRraph.h
#pragma once
#include<iostream>
using namespace std;
//邻接矩阵存储有向网
#define Mvnum 100 //最大顶点数
typedef char VerType; //顶点数据类型
typedef int ArcType; //弧的权值
typedef struct AMGraph {
int vexnum, arcnum;
VerType vexs[Mvnum]; //顶点信息表
ArcType arcs[Mvnum][Mvnum]; //邻接矩阵
}AMGraph;
//创建有向网
void CreateUDN(AMGraph& G);//文件名为：AMGraph.cpp
#include"AMGraph.h"
//用邻接矩阵创建有向网
void CreateUDN(AMGraph& G)
{
//inf表示两顶点间没有线路，距离为无穷大
int inf = 99999999;
//输入顶点与弧的个数
cin >> G.vexnum >> G.arcnum;
//判断合法性
if (G.vexnum > Mvnum || G.arcnum > (G.vexnum - 1) * G.vexnum)
{
cout << "所输入信息非法" << endl;
return;
}
//输入顶点的信息，类型为char
for (int i = 0;i < G.vexnum;i++)
{
cin >> G.vexs[i];
}
//将图的边初始化
for (int i = 0;i < G.vexnum;i++)
{
for (int j = 0;j < G.vexnum;j++)
{
if (i != j)
G.arcs[i][j] = inf;
else
G.arcs[i][j] = 0;
}
}
//输入权值
for (int i = 0;i < G.arcnum;i++)
{
//输入v1,v2作为弧<v1,v2>的顶点以及该弧权值w
//顶点下标从0开始
int v1, v2, w;
//此处省略了查找v1,v2编号的过程
cin >> v1 >> v2 >> w;
//判断合法性
if (v1 == v2 || v1 >= G.vexnum || v2 >= G.vexnum
|| v1 < 0 || v2 < 0)
{
i--;
continue;
}
if (G.arcs[v1][v2] != inf)
{
i--;
continue;
}
//输入弧<v1,v2>的权值
G.arcs[v1][v2] = w;
}
//创建完毕
}
DIJ算法实现
//文件名为：DIJ.h
#pragma once
#include"AMGraph.h"
/*
迪杰斯特拉算法利用了“中转”点不断更新最短路径,
直到求出源点到顶点的所有最短路径
我们知道，又是从某一个顶点到达另外一个顶点或根本不存在路径，
或直达路径会大于源点到中转点路径加上中转点到终点的路径，
此时需要将源点到终点的距离更新
*/
//辅助数组初始化函数
void Init(const AMGraph& G, int* Path, int* shortestDis, const int& v, bool* S);
//寻找最短路径<v,vk>的下标k
int findmin(const int* shortestDis, const bool* S, const int& n);
//结束更新，输出最短路径：
void OutshortestPath(const int& v, const int* shortestDis, const int* Path, const AMGraph& G);
//输出该路径上的顶点
void OutvexInpath(const int& v, const int& i, const int* Path, const AMGraph& G);
//计算某源点到其他所有顶点的最短路径
//以邻接矩阵作为存储结构
void ShortestPath_DIJ(const AMGraph& G, const int& v);//文件名为：DIJ.cpp
#include"DIJ.h"
//inf表示两顶点间没有线路，距离为无穷大
int inf = 99999999;
//辅助数组初始化函数
void Init(const AMGraph& G, int* Path, int* shortestDis, const int& v ,bool*S)
{
//如果<v,vi>之间有弧，那么vi的直接前驱为v
for (int i = 0;i < G.vexnum;i++)
{
if (inf != G.arcs[v][i])
Path[i] = v;
else
Path[i] = -1;
}
//初始化源点到各个顶点之间的最短路径
for (int i = 0;i < G.vexnum;i++)
{
shortestDis[i] = G.arcs[v][i];
}
//v自然在最短路径源点集中
S[v] = true;
}
//计算某源点到其他所有顶点的最短路径
int findmin(const int* shortestDis, const bool* S,const int&n)
{
int k = 0;
int minroad = inf;
for (int i = 0;i < n;i++)
{
if (!S[i])
{
if (minroad > shortestDis[i])
{
k = i;
minroad = shortestDis[i];
}
}
}
return k;
}
//输出该路径上的顶点
void OutvexInpath(const int& v, const int& i, const int* Path, const AMGraph& G)
{
//查找到源点v为止
if (i == v)
{
cout << G.vexs[v];
}
else
{
//查找下标为i的顶点的直接前驱
OutvexInpath(v, Path[i], Path, G);
cout << "->" << G.vexs[i];
}
}
//结束更新，输出最短路径：
void OutshortestPath(const int& v, const int* shortestDis, const int* Path, const AMGraph& G)
{
cout << "最短路径输出如下:>" << endl;
for (int i = 0;i < G.vexnum;i++)
{
cout << "从顶点" << G.vexs[v] << "到顶点" << G.vexs[i] << "的最短路径为" << shortestDis[i] << endl;
//输出该路径上的顶点
cout << "其路径如下:>" << endl;
OutvexInpath(v, i, Path, G);
//输出换行
cout << endl;
}
}
//以邻接矩阵作为存储结构
void ShortestPath_DIJ(const AMGraph& G, const int& v)
{
//判断下标的合法性
if (v > G.vexnum || v < 0)
{
return;
}
//首先定义辅助数组
//1.记录该顶点是否已经加入最短路径终点集合
bool S[Mvnum] = { 0 };
//2.记录源点v0到终点vi的最短路径上，vi的直接前驱顶点在邻接矩阵中的下标
int Path[Mvnum] = { 0 };
//3.记录当前源点到各个终点的最短路径
int shortestDis[Mvnum] = { 0 };
Init(G, Path, shortestDis, v, S);
//有向网的顶点个数
int n = G.vexnum;
//将其余n-1个顶点加入到S中
for (int i = 1;i < n;i++)
{
//寻找当前源点到没加入S集中的顶点的最短路径(v,vk)
//并且返回其下标k
int k = findmin(shortestDis, S, n);
//将k下标加入到S集
S[k] = true;
//通过“中转点”k,更新最短路径
for (int j = 0;j < n;j++)
{
if (!S[j])
{
//需要用到<v,k>的最新数据作为判断依据
if (shortestDis[j] > shortestDis[k] + G.arcs[k][j])
{
//更新最短路径
shortestDis[j] = shortestDis[k] + G.arcs[k][j];
//更新j的直接前驱为k
Path[j] = k;
}
}
}
}
//结束更新，输出最短路径：
OutshortestPath(v, shortestDis, Path, G);
}
//本例可以优化的地方为：定义G,Path,Shortest,S的存储结构为全局变量
//从而减少函数参数本案例代码可以优化的方面就是，可以直接定义G,Path,Shortest,S等变量为全局变量，从而减少函数的参数个数。
测试代码
//文件名为:test.cpp
#include"DIJ.h"
void test()
{
AMGraph G;
CreateUDN(G);
ShortestPath_DIJ(G, 0);
}
int main()
{
test();
return 0;
}测试结果
算法分析
就空间复杂度而言，由于借助了三个辅助数组，而且数组的大小均为Mvnum(邻接矩阵能够存储的最大顶点个数)，故空间复杂度为O（Mvnum）。当然，若n表示顶点个数，如果选择动态开辟内存，则空间复杂度为O(n);
就时间复杂度而言，n依旧表示顶点个数，主循环需要扫描n-1次，而无论是查找最小权值边或通过中转点更新最短路径，都需要扫描n次，故时间复杂度为O(n^2).若采用邻接表作为存储结构，那么即使更新最短路径的时间会减少（在新加入最短路径集的终点k的邻接表上扫描有限的边，而非扫描n次），当时由于选择最小分量的时间不减，故时间复杂度依旧为O(n^2).文章来源：https://www.toymoban.com/news/detail-760089.html
最后说明
即使现实生活中我们只需要源点到特定顶点的最短路径，但是其与求解单源点到达其余全部顶点的最短路径问题一样复杂.文章来源地址https://www.toymoban.com/news/detail-760089.html
到了这里，关于最短路径——迪杰斯特拉算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
