目录

迪杰斯特拉算法介绍

算法知识点

算法思路

算法前的准备

算法步骤

模板代码

例题带图解析

正文

迪杰斯特拉算法介绍

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

迪杰斯特拉算法用于查找图中某个顶点到其它所有顶点的最短路径，该算法既适用于无向加权图，也适用于有向加权图。

注意，使用迪杰斯特拉算法查找最短路径时，必须保证图中所有边的权值为非负数，否则查找过程很容易出错。

算法知识点

贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心算法不要回溯

算法思路

通过Dijkstra计算图G中的最短路径时，需要指定一个起点D(即从顶点D开始计算)。

此外，引进两个数组S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点D的距离)。

初始时，数组S中只有起点D；数组U中是除起点D之外的顶点，并且数组U中记录各顶点到起点D的距离。如果顶点与起点D不相邻，距离为无穷大。

然后，从数组U中找出路径最短的顶点K，并将其加入到数组S中；同时，从数组U中移除顶点K。接着，更新数组U中的各顶点到起点D的距离。

重复第4步操作，直到遍历完所有顶点。

算法前的准备

需要借助三个辅助向量（数组）：

       v：表示以v为下标的起点

   1.数组 s[n] 标记这个最短路径有没有被求出

       s[i] = 1; 当源点v到vi的最短路径求出

       s[i] = 0; 源点v到vi的最短路径没有被求出

           s[0]: 表示v->v0的最短路径有没有被求出

           s[1]: 表示v->v1的最短路径有没有被求出

           s[2]: 表示v->v2的最短路径有没有被求出

           ....

           s[i]: 表示v->vi的最短路径有没有被求出

                初始时，s[v] = 1,其它的s[i] = 0

   2.数组dist[n]  最短路径距离

       dist[i] 源点v到vi的最短路径长度

           初始时：

               dist[i] = <v,vi> = w;

               <v,vi>的权w，若p(v,vi)存在，表示v到vi有一条直接路径

               dist[i] = VERY_BIG ,p(v,vi)不存在，表示v到vi没有一条直接路径

   3.path[n]

       源点v到vi的最短路径  (v,...vi)

           初始时，path[i] = {v}

算法步骤

假设图中有n个顶点，Dijkstra是要求n-1条最短路径，即源点v到其它n-1个顶点的边（最短路径）

       step1:

           源点v到其它各个顶点的第一条最短路径长度 dis[u] = MIN{dist[w]| w= 0,1,2..n-1且s[w] = 0}

           表示：

               在所有没有被找到最短路径中找到一条最短的，这条路径当做当前求出的最短路径长度。

               eq: dist[B] = Min{dis[B], dist[C],dist[D]}

                   假设dist[B]为最短路径

                       即A-B （源点A）的最短路径为dist[B] 且 s[B] = 1;

                           证明：

                               A->B

                               用穷举法：

                                   A->B : dist[B]

                                   A->C->B :dist[c] + x  > dist[B]

                                   所以得证。

                                   dist[u]最为当前最短路径 s[u] = 1：表示v->u的最短路径已经被求出。

       step2:

           对所有s[w] = 0(其它所有未被求出的最短路径的点)，更新dist[w]

               if dist[u] + <u , w> < dist[w] //说明我有一条更短的路径到w

                   dist[w] = dist[u] + <u , w> //即更新dist[w]

                   把step1 step2 重复n-1次 就可以求出最短距离

模板代码

int s[MAXN];//是否已经求出最短路径的标志数组 s[i]==1 :表示v到vi最短路径已经求出 ； s[i] == 0:表示v到vi最短路径没有求出
int dist[MAXN];//存放当前源点到各顶点的最短路径长度
int path[MAXN];//存放的源点到终点i的最短路径是利用哪个最优点更新的 
//用迪杰斯特拉算法求出v点到其它各顶点的最短路径
void Dijkstra(Graph *g, int v)
{
    //step 1 初始化辅助数组
    int i;
    for( i = 0; i < g->vexnum; i++)
    {
        s[i] = 0;//一开始都为0
        dist[i] = g->Adj[v][i];//邻接矩阵权值
        path[i] = v;//每条最短路径起点都为v
    }
    s[v] = 1;
    dist[v] = 0;
    //step2 在所有没有被求出来的最短路径找出一条最短的 长度当成当前求出的最短路径
    int min;//求最优顶点的记录板
    int i_min;//最优顶点下标
    int times; //寻找最短路径的次数  每次只找一条n-1
    for(times = 0; times < g->vexnum-1; times++)
    {
        //step1 求出当前最优顶点
        min = VERY_BIG;
        for(i = 0; i < g->vexnum; i++)
        {
            if(s[i] == 0 && dist[i] < min)
            {
                min = dist[i];
                i_min = i;
            }
        }
        s[i_min] = 1;//最短路径已经求出
        //step2 根据最优顶点更新其它dist
        for(i = 0; i < g->vexnum; i++)
        {
            if(s[i] == 0)
            {
                if(dist[i_min] + g->Adj[i_min][i]  < dist[i])
                {
                    dist[i] = dist[i_min] + g->Adj[i_min][i];
                    path[i] = i_min;
                }
            }
        }
    }
}
// a -> b: 15 输出所有最短路径值
void print_dist(Graph *g, int v)
{
    int i;
    for(i = 0; i < g->vexnum; i++)
    {
        printf("the %c -> %c : %d\n",g->V[v], g->V[i], dist[i]);
    }
}
void print_path(Graph *g, int v)
{
    int i;
    for(i = 0; i < g->vexnum; i++)
    {
        if(dist[i] == VERY_BIG)
        {
            printf("%c -> %c is no path\n",g->V[v], g->V[i]);
            continue;
        }
    }
    printf("%c ->%c : %c",g->V[v], g->V[i],g->V[i]);
    int pre_index = path[i];
    while(1)
    {
        printf("%c ",g->V[pre_index]);
        if(pre_index == v)//已经回到了出发点
        {
            break;
        }
        pre_index = path[pre_index];
    }
    printf("\n");
}

例题带图解析

例题来源，自创，是笔者经过计算后，包含了大部分情况。                                                    （求A点到各点的最短路径）

名称解释：

       标志：为1 时表示已找到最短路径，为0 时表示还未找到最短路径

       距离：目前从A点到目的点的最短距离

       路径：目前从A点到目的点的最短路径

       --：目前无法到达

这是第一轮寻路，以A为起点。

上述距离最短的是A->C为2，因此C的最短路径找到了,C的标志为变为1，下一轮以A->C这条路径为起点，继续寻路

第二轮寻路，以A->C为起点，图中可以看出，C继续往下走，可以到D点与F点。

比较距离时，比较的是标志位为0的有数距离，第二轮就算比较B，D，F三点距离，这里可以看到A->B距离最小，因此到B点的最小路径找到，为A->C，距离为2。下一轮以A->C这条路径为起点，继续寻路。

后面的与这两步都一样，这里就不赘述啦，就留一点给小伙伴们发挥的空间，也可以将自己后续的寻路步骤发到评论区大家一起讨论哦。互通有无，互相进步。