案例引入

日常生活中常常涉及最短路径问题，如在一个城市交通网中，如何选取从起点到达终点的路径，才能使这一趟旅程的路程最短？或所需时间最少？或所需交通费用最低？诸如此类问题都可以抽象为求解图的最短路径问题。我们把图的顶点表示为城市的交通站点，边表示交通站点间的路径，边的权值表示为交通站点间的路径的距离、所需时间或费用等等，则上述问题放映到图上就是，如何求解图顶点间权值之和最小的路径。

由于城市交通站点间具有方向性，故常选取带权值的有向网表示城市交通网。习惯上，在有向网的一条路径中，第一个顶点被称为源点，最后一个顶点被称为终点。

常见的最短路径问题分为两类：单源点到达其余顶点的最短路径以及任意一对顶点间的最短路径。

求解单源点到其余顶点的最短路径问题

迪杰斯特拉算法(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).

最后说明

即使现实生活中我们只需要源点到特定顶点的最短路径，但是其与求解单源点到达其余全部顶点的最短路径问题一样复杂.