引言

日常生活中，当我们出去旅游、办事等等，面对陌生的环境，我们常常需要规划自己的路线，来使移动的距离最短或是开销最低。那么，今天给大家简单介绍一种针对网图的最短路径算法——迪杰斯特拉算法。

最短路径：即起点和终点之间经过的边上权值(Weight)之和最小的路径。

算法思想

在这里插入图片描述给我们一个这样的网图，假如让我们求从v0到v2的最短路径，我们可以看到路线v0->v2的长度为5，同时我们也可以很轻易的发现v0->v1->v2的长度为4，比5更短。
其中：v0->v1为v0到v1的最短路径，且v1与v2邻接。我们怎么知道其他路径，例如v0->v1->v4->v2不是最短路径呢，显然该网不是。
但是在实际求解中，我们也是求得v0到v4最短距离再加上v4->v2的距离跟其它v0到v2的邻接点的最短距离加上该邻接点到v2的直接距离作比较，较小者为当前最短路径。

请注意这个“当前”，也就是说这个算法是不断求解并更新当前最短路径，最后获得正确结果的算法。

例如：
我们以v0为起点，首先我们发现最短路径为v0->v1，于是我们选择v1，寻找v1的邻接点(不包括已经求得最短路径的v0,显然v0->v0 = 0为最短路径)，v1邻接v2、v3、v4，那么我们得到，若以v1为前驱顶点，到达v2的距离为1 + 3 = 4，到达v3距离为8，v4为6。
第二步，已有最短路径的点为v0和v1，接下来继续寻找v0和v2的当前最短路径(可通过已知含最短路径的点)，也就是v0->v1->v2的4，然后我们更新当前驱顶点为v2时，v0到v4和v5的距离。

好了，现在我们对这个算法已经有了一定的了解，请看百度百科的定义。

G={V,E}

初始时令 S={V0},T=V-S={其余顶点}，T中顶点对应的距离值 [1]
若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值 [1]
若不存在<V0,Vi>，d(V0,Vi)为∞ [2]

从T中选取一个与S中顶点有关联边且权值最小的顶点W，加入到S中 [1]

对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值 [1]
重复上述步骤2、3，直到S [1] 中包含所有顶点，即W=Vi为止 [1]

迪杰斯拉算法是一个按路径长度递增的次序产生最短路径的算法

迪杰斯拉算法类似贪心算法，即每一步只考虑当前最优选择，把每一步的最优解看做总体的最优解，尽管它并不是一定正确的。
不过，迪杰斯拉算法会不断的修正这个每一小步的最优解，从而是最终答案是正确的。

实现

本篇网的存储采用邻接矩阵(Adjacency matrix)，即以一个对应边的二维数组（称之为矩阵）和一个对应顶点表的一维数组来存储网的结构体。
我们把一维数组称为vex[]，二维数组称之为arc[][]。
一维数组存储类型由顶点决定，这里我们假设为char类型。
vexs[0] == ‘a’的含义为：下标为0的顶点名称叫做’a’。
二维数组arc[1][2]的含义为：从顶点v1到顶点v2的距离

同时为了算法实现方便，我们约定：矩阵中存储的值，无穷代表两点不邻接，有限正整数代表权值，若为0则代表起点终点相同。(无穷的原因是便于更新代表最短路径的数组，这点接着阅读就能体会到，这也是一般算法的常见做法)。

我们用D[v]来存v0到v的最短路径长度，P[v]存求得当前最短路径时的前驱顶点下标，final[v]来表示是否为最终的最短路径。
例如：D[2] = 4 , P[2] = 1 ，final[2] = 1分别表示v0到v2最短路径为2，最短时的前驱顶点为v1，v2已经找到最短路径。

代码

MGraph.c (M表示矩阵Matrix)

//邻接矩阵
#include <stdio.h>

#define MAXSIZE 100
#define INFINITY 65535  //表示无边(Weight有时为0，不用0表示)

typedef char VertexType;

typedef int EdgeType;

typedef struct
{
    VertexType vexs[MAXSIZE];   //顶点表
    EdgeType arc[MAXSIZE][MAXSIZE]; //邻接矩阵
    int numVertexes, numEdges;  //顶点数和边数
}MGraph;

void CreateMGraph(MGraph *G)
{
    int i, j, k, w;
    printf("输入顶点数和边数:\n");
    scanf("%d%d", &G->numVertexes, &G->numEdges);
    for (i = 0; i < G->numVertexes; i++)
        scanf("%c", &G->vexs[i]);
    //初始化邻接矩阵
    for (i = 0; i < G->numVertexes; i++)
        for (j = 0; j < G->numVertexes; j++)
            G->arc[i][j] = INFINITY;
    for (k = 0; k < G->numEdges; k++)
    {
        printf("输入边(vi, vj)的下标i和上标j和权w:\n");
        scanf("%d%d%d", &i, &j, &w);
        G->arc[i][j] = w;
        G->arc[j][i] = G->arc[i][j];   //无向图矩阵对称
    }
}

Dijkstra.c

//迪杰斯特拉算法生成最短路径
//求解有向网G的v0顶点到其余顶点v最短路径P[v]及带权长度D[v]
//P[v]:前驱下标顶点，D[v]:v0到v的最短路径长度

#include "MGraph.c"

#define  MAXVEX 9

typedef int Patharc[MAXVEX];    //存储最短路径下标
typedef int ShortPathTable[MAXVEX]; //最短路径权值和

void Dijkstra(MGraph G, int v0, Patharc *P, ShortPathTable *D)
{
    int v, w, k, min;
    int final[MAXVEX];  //final[w]=1表示求得v0至vw最短路径
    //初始化数据
    for (v = 0; v < G.numVertexes; v++)
    {
        final[v] = 0;
        (*D)[v] = G.arc[v0][v]; //将与v0有连线的顶点加上权值
        (*P)[v] = 0;
    }
    (*D)[v0] = 0;
    final[v0] = 1;
    //每次求得v0到某个顶点的最短路径
    for (v = 1; v < G.numVertexes; v++)
    {
        min = INFINITY;	//无穷大值
        //找到当前离v0最近的点(未求得最短路径的)，用k记录其下标
        for (w = 0; w < G.numVertexes; w++)
        {
            if (!final[w] && (*D)[w] < min)
            {
                k = w;
                min = (*D)[w];
            }
        }
        final[k] = 1;
        //修正邻接点当前最短路径及距离
        for (w = 0; w < G.numVertexes; w++)
        {
        	//若以w为前驱顶点的路径更短，更新路径和放有前驱顶点的数组P[v]
            if (!final[w] && (min + G.arc[k][w] < (*D)[w]))
            {
                (*D)[w] = min + G.arc[k][w];
                (*P)[w] = k;
            }
        }
    }
}

参考书籍

《大话数据结构》

C语言：迪杰斯特拉(Dijkstra)算法

目录

引言

算法思想

实现

代码

参考书籍