Dijkstra算法：最短路径的C语言代码实现及应用

在网络路由问题的解决中，寻找从图的一个点到另一个顶点的最短路径或最小权重路径是一个非常重要的过程。

形式化表示为有向带G=(V,E)，V中从点s到顶点t的最短路径是S中E的边中连接s到t的最小成本路径。

当S发现，我们已经解决了一对最短路径问题。为此，我们实际上需要首先解决更一般的单源最短路径问题。单源最短路径问题是求解单对顶点最短路径过程的一部分。在单源最短路径问题中，计算从顶点s到其他相邻点的最短路径。之所以采用该方法来解决这个问题，是因为没有其他更好的方法来解决单顶点最短路径问题。

Dijkstra 算法

解决单源最短路径问题的方法之一是Dijkstra 算法。

Dijkstra 算法创建一棵最短路径树，树的根是起点 s，树的分支是从点 s 到图 G 中所有其他点的最短路径。该算法要求图中的所有权重都是非负的。与Prim算法一样，Dijkstra算法也是一种利用贪心算法进行计算并最终产生最优结果的算法。

基本上，Dijkstra 算法通过选择一个顶点并不断探索连接到该顶点的边来确定到每个顶点的最短路径是否最优。该算法与广度优先搜索算法类似，它首先遍历与该顶点相连的所有顶点，然后再探索图中更深的顶点。为了计算 s 与所有其他顶点之间的最短路径，Dijkstra 算法必须存储每个顶点的颜色值和最短路径的估计。通常，最短路径估计由变量 d 表示。

首先将所有颜色值设置为白色，并将最短路径估计设置为 ∞（表示比图中所有边的权重大的足够大的数字）。将起点的最短路径估计设置为0。随着算法的发展，最短路径树的每个顶点（不包括起点）都会分配一个顶节点。在算法终止之前，顶点的头节点可以更改多次。

Dijkstra算法的运行过程如下：

首先在图的所有白色顶点中，选择最短路径估计最小的点u。最初，最短路径估计设置为 0 的顶点被用作起点。选择这个顶点后，将其涂成黑色。

沿着 在 u 旁边的每个顶点 v 处，释放其边 (u, v) 。释放边缘后，我们要确认是否要更新到目前为止计算出的最短路径。方法是在u的最短路径估计上加上(u,v)的权重。如果该总值小于或等于 v 的最短路径估计，则将此值分配给 v 作为新的最短路径估计。 同时设置u v为主结。

重复此操作，直到所有顶点都标记为黑色。一旦计算出最短路径树，就可以明确地确定从 s 到另一个顶点 t 的最短路径：从树中的节点 t 开始，搜索后续的头节点，直到到达 s。该搜索路径的反向路径是从 s 到 t 的最短路径。

下图展示了计算图上a到其他点的最短路径的过程。例如，从 a 到 b 的最短路径为 (a, c, f, b)，权重为 7。最短路径估计和每个顶点的父节点显示在每个顶点旁边。最短路径估计显示在对角线左侧，父节点显示在对角线右侧。浅灰色的边是最短路径树生长过程中的边。

最短路径 UI 定义

shortest

int Shortest(Chart *graph, const PathVertex *start, List *paths, int (*correspondence)(const void *key1, const void) ;

返回值：如果计算成功，返回0；否则返回-1

说明 ：用于计算该顶点的原点到该顶点的所有其他顶点之间的最短路径有向带 权图 图。该函数改变了图，因此如有必要，请在调用该函数之前对图进行备份。

每个图顶点必须包含 PathVertex 类型的数据。通过设置PathVertex结构体中成员的权重值，权重weightt值由传递给graph_ins_edge参数的参数data2决定，使用PathVertex结构体成员data来存储与顶点相关的信息，如顶点标识符等。

图匹配函数（当使用graph_init函数初始化图时调用该函数）用于比较PathVertex结构的数据成员。该功能与最短传递参数匹配相同。

计算完成后，将最短路径的相关信息返回给paths，它是一个PathVertex结构体的列表。在路径中，起始点的主节点设置为NULL。彼此顶点的父成员都指向该顶点之前的顶点，该顶点位于距起点的最短路径上。路径的顶点指向图的实际顶点，因此只要路径可用，函数调用就必须确保图的内存空间有效。当不再使用路径时，通过调用list_destroy销毁路径。

复杂度：O(EV2)，其中V是图中的顶点数量，E是边标签的数量。

最短路径实现与分析

计算从有向区的权图顶点到所有其他顶点的最短路径，图的表示与最小生成树中的相同。只需将顶点 MstVertex 结构替换为 PathVertex 结构即可。

PathVertex 可以表示树形图，可以跟踪 Dijkstra 算法所需的顶点和边信息。 该结构体有5个成员：data是与顶点相关的数据；重量是边缘到达尖端的重量； color 是笔尖颜色； d是顶点最短路径估计；父级是最短路径交汇处的顶点。

构建包含Patavertex结构的图的过程与构建包含MstVertex结构的图相同。

最短操作首先初始化邻接表结构的链表中的每个点。将每个顶点的最短路径估计初始化为 DBL_MAX（起始点除外，其初始化为 0.0）。顶点颜色值、最短路径估计和根节点使用存储在邻接列表结构的链接列表中的点来维护。原因与计算最小生成树时解释的相同。

Dijkstra 算法的本质是对图的每个节点使用一个循环来迭代一次。在每次迭代期间， 首先选择所选白点中具有最小最短路径估计的顶点 。 同时将邻接表结构的链表中的该顶点涂黑。 接下来，迭代选定顶点旁边的顶点。 当每个顶点被传输时，在邻接表结构的链表中检查其颜色和最短路径估计。一旦获得此信息，就调用松弛来释放所选顶点和相邻顶点之间的边。如果在此过程中发现需要更新相邻顶点的最短路径估计和父节点，则更新邻接表结构的链表中的该顶点。重复此过程，直到所有顶点都被漆成黑色。

当Dijkstra算法的主循环结束时，从起点到图中所有其他点的最短路径的计算就完成了。此时，将邻接表结构的链表中的每个黑色PathVertex结构添加到链表路径中。 路径中，主节点为NULL的顶点为起点。每个顶点的头成员都指向前一个顶点，从起点开始的路径最短。每个PathVertex结构的权重成员不经常使用，因为它仅在存储在邻接表中时使用。 下图显示了计算上面图1中的最短路径时返回的PathVertex结构列表。

示例：最短路径计算实现

/*shortest.c*/
#include <float.h>
#include <stdlib.h>

#include "graph.h"
#include "graphalg.h"
#include "list.h"
#include "set.h"

/*relax  释放边、更新最短路径估计值、更新父结点*/
static void relax(PathVertex *u, PathVertex *v, double weight)
{
    /*释放顶点u和v之间的边*/
    if(v->d > u->d + weight)
    {
        v-> = u->d + weight;
        v->parent = u;
    }
    return;
}

/*shortest  最短路径计算函数*/
int shortest(Graph *graph, const PathVertex *start, List *paths, int (*match)(const void *key1, const void key2))
{
    AdjList *adjlist;
    PathVertex *pth_vertex, *adj_vertex;

    ListElmt *element, member;
    double minimum;
    int found,i;

    /*初始化图中的所有顶点*/
    found = 0;

    for(element = list_head(&graph_adjlists(graph)); element != NULL; element = list_next(element))
    {
        pth_Vertex = ((AdjList *)list_data(element))->vertex;

        if(match(pth_vertex, start))
        {
            /*找到并初始化起始顶点*/
            pth_vertex->color = white;
            pth_vertex->d = 0;
            pth_vertex->parent = NULL;
            found = 1;
        }
        else
        {
            /*非起始顶点，初始化*/
            pth_vertex->color = white;
            pth_vertex->d = DBL_MAX;
            pth_vertex->parent = NULL;
        }
    }

    /*如果未匹配到起始顶点，程序退出*/
    if(!found)
        return -1;

    /*使用Dijkstra算法计算从起始顶点开始的最短路径*/
    i=0;

    while(i < graph_vcount(graph))
    {
        /*从所有的白色顶点中，选择最短路径估计值最小的顶点*/
        minimum = DBL_MAX;

        for(element=list_head(&graph_adjlists(graph)); element!=NULL; element = list_next(element))
        {
            pth_vertex = ((AdjList*)list_data(element))->vertex;

            if(pth_vertex->color == white && pth_vertex->d < minimum)
            {
                minimum = pth_vertex->d;
                adjlist = list_data(element);
            }
        }

        /*将该顶点涂成黑色*/
        ((PathVertex *)adjlist->vertex)->color = black;

        /*遍历与所选顶点相邻的顶点*/
        for(member=list_head(&adjlist->adjacent); member != NULL; member = list_next(member))
        {
            adj_vertex = list_data(member);

            for(element = list_head(&graph_adjlists(graph)); element != NULL; element = list_next(element))
            {
                pth_vertex = ((AdjList *)list_data(element))->vertex;

                if(match(pth_vertex, adj_vertex))
                {
                    relax(adjlist->vertex, pth_vertex, adj_vertex->weight);
                }
            }
        }
        i++;
    }
    /*将邻接表结构链表中每个黑色PathVertexx结构体插入链表paths中*/
    list_init(paths,NULL);

    for(element=list_head(&graph_adjlists(graph)); element!=NULL; element=list_next(paths,NULL))
    {
        /*加载邻接表结构链表中的每一个黑色顶点*/
        pth_vertex=((AdjList *)list_data(element))->vertex;

        if(pth_vertex->color == black)
        {
            if(list_ins_next(paths, list_tali(paths), pth_vertex) != 0)
            {
                list_destroy(paths);
                return -1;
            }
        }
    }
    return 0;
}

最短路径示例：路由表

现实中，最短路径算法一个非常重要的应用就是互联网上的数据路由

。路由是一种决策过程，其中数据从一个点传输到另一个点。在互联网中，路由是在称为网关的互连点之间分发数据段或数据包的过程。当数据包经过网关时，路由器会查看数据包的最终目的地并将数据包转发到下一个网关。路由器的作用是将数据包发送到距离目的地最近的位置。

为了将数据包发送到最近的目的地，每个路由器必须维护互联网的结构或拓扑信息。该信息存储在路由表中。路由表存储路由器知道如何到达的每个网关的条目。每个条目指定数据发送到的下一个网关的地址。

由于路由器会随着互联网的变化定期更新其路由表，因此数据包会沿着最佳可能的路由发送。 有一种路由称为最短路径优先路由或SPF路由，其中​​每个路由器维护自己的网络图，通过计算自身与其他节点之间的最短路径来更新其路由表。 。 互联网的拓扑图是一个有向带状图，其顶点是网关，边是网关之间的连接线。边缘的权重由连接路径的性能决定。有时路由器会交换拓扑和性能信息，并且为此目的设计了协议。

设计一个功能路由，使用 SPF 路由算法来计算更新路由表中的条目所需的信息。

此函数接受路径数据列表，该列表在最短路径参数中返回。

它使用此信息来确定路由器应将数据包发送到的下一个网关，并确保该网关距离目的地更近一步。

要填充指定网关 的完整表，必须首先调用最短函数，其中网关以起始参数 传递。

接下来，对于路由表中的每个目标地址，调用函数route，其中传递目标地址。

然后将此地址作为匹配函数传递到从 paths 创建的路径的 graph_init 函数中。

route函数将路径目标列表中的主节点指针指向网关，并返回发送数据包的最佳节点（该节点接下来存储在输出参数中）。在后面的点中，顶部点会返回到路径的实际顶部，因此只要下一个点仍然可以访问，路径中的内存空间就一定是有效的。

下图A部分展示了路由器在Internet上的路由表计算过程。 B 部分显示了路由器处理中的路由表计算过程 b. 请注意，最短路径根据 Internet 上的起始位置而变化。还应该注意的是，在图B中不可能到达a，因此表中没有相关条目。

计算路由的时间复杂度为O(n2)，其中n是路径中网关的数量。

示例：更新路由表条目的功能实现

/*route.c*/
#include <stdlib.h>
#include "graphalg.h"
#include "list.h"
#include "route.h"

/*route*/
int route(List *paths, PathVertex *destination, PathVertex **next, int (*match)(const void *key1, const void *key2))
{
    PathVertex *temp,
               *parent;
    ListElmt   *element;
    int        found;

    /*查找位于网关链表中的目的地址*/
    found = 0;

    for(element = list_head(paths); element != NULL; element = list_next(element))
    {
        if(match(list_data(element),destination))
        {
            temp = list_data(element);
            parent = ((PathVertex *)list_data(element))->parent;
            found = 1;
            break;
        }
    }

    /*如未发现目标地址，函数退出*/
    if(!found)
        return -1;

    /*计算到目的地最短路径的下一个网关*/
    while(parent!=NULL)
    {
        temp = list_data(element);
        found = 0;

        for(element = list_head(paths); element != NULL; element = list_next(element))
        {
            if(match(list_data(element),parent))
            {
                parent = ((PathVertex *)list_data(element))->parent;
                found = 1;
                break;
            }
        }

        /*如果目标不能到达，函数退出*/
        if(!found)
            return -1;
    }
    *next = temp;

    return 0;
}