C语言实现迪杰斯特拉算法详解

创作时间:

作者:

@小白创作中心

C语言实现迪杰斯特拉算法详解

引用

CSDN

https://blog.csdn.net/ZGUIZ/article/details/54645019

迪杰斯特拉算法（Dijkstra算法）是用于求解图中单源最短路径的经典算法。它广泛应用于网络路由、地图导航等领域。本文将通过C语言实现，详细讲解迪杰斯特拉算法的原理和实现步骤。

1. 数据结构定义

首先，我们需要定义一些基本的数据结构和常量：

#define OK 1
#define ERROR 0
#define MVNum 100
#define Max_Int 32726
typedef int Status;
typedef int ArcType;
typedef char VerTexType;
typedef struct{
    VerTexType vex[MVNum];
    ArcType arc[MVNum][MVNum];
    int vexnum, arcnum;
}AMGraph;

这里定义了一个邻接矩阵表示的图结构AMGraph，其中vex数组存储顶点信息，arc数组存储边的权值，vexnum和arcnum分别表示顶点数和边数。

2. 全局变量声明

我们还需要两个全局变量来辅助算法的实现：

int Path[MVNum];
ArcType D[MVNum];

Path[]用于记录到达每个顶点的上一个顶点。
D[]用于记录从源点到每个顶点的最短路径的权值。

3. 图的创建函数

接下来是创建有向图的函数：

int LocateVex(AMGraph *G, VerTexType v)
{
    int i;
    for (i = 0; i < G->vexnum; i++)
    {
        if (G->vex[i] == v)
            return i;
    }
    return -1;
}
Status CreateUDN(AMGraph *G)
{
    VerTexType v1, v2;
    ArcType w;
    int i, j, k;
    printf("输入总节点数、总边数：");
    scanf("%d %d", &G->vexnum, &G->arcnum);
    printf("输入节点的值：");
    fflush(stdin);
    for (i = 0; i < G->vexnum; i++)
    {
        scanf("%c", &G->vex[i]);
    }
    for (i = 0; i < G->vexnum; i++)
    for (j = 0; j < G->vexnum; j++)
    {
        G->arc[i][j] = Max_Int;
    }
    for (k = 0; k < G->arcnum; k++)
    {
        fflush(stdin);
        printf("依次输入边的两个顶点以及边的权值：");
        scanf("%c %c %d", &v1, &v2, &w);
        i = LocateVex(G, v1);
        j = LocateVex(G, v2);
        G->arc[i][j] = w;
    }
    return OK;
}

这个函数首先读取图的顶点数和边数，然后依次读取每个顶点的值，初始化邻接矩阵，并读取每条边的两个顶点和权值。

4. 迪杰斯特拉算法实现

核心算法实现如下：

void ShortestPath_DIJ(AMGraph G, int v0)
{
    int min, i, w, v;
    bool S[MVNum];
    for (v = 0; v < G.vexnum; v++)
    {
        S[v] = false;
        D[v] = G.arc[v0][v];
        if (D[v] < Max_Int)
            Path[v] = 0;
        else
            Path[v] = -1;
    }
    S[v0] = true;
    D[v0] = 0;
    for (i = 1; i < G.vexnum; i++)
    {
        min = Max_Int;
        for (w = 0; w < G.vexnum; w++)
        {
            if (!S[w] && min>D[w])
            {
                v = w;
                min = D[w];
            }
        }
        S[v] = true;
        for (w = 0; w < G.vexnum; w++)
        {
            if (!S[w] && D[w]>D[v] + G.arc[v][w])
            {
                D[w] = D[v] + G.arc[v][w];
                Path[w] = v;
            }
        }
    }
}

算法的主要步骤包括：

初始化：将所有顶点标记为未访问，将源点到其他顶点的初始距离设置为邻接矩阵中的值，如果存在边则设置为边的权值，否则设置为无穷大。
选择当前未访问顶点中距离源点最近的顶点，标记为已访问。
更新从源点到其他未访问顶点的距离，如果通过当前顶点可以得到更短的路径，则更新距离和路径信息。
重复步骤2和3，直到所有顶点都被访问。

5. 主函数

最后是主函数的实现：

int main(void)
{
    int i, j;
    AMGraph G;
    CreateUDN(&G);
    ShortestPath_DIJ(G, 0);
    for (i = 1; i < G.vexnum; i++)
    {
        if (D[i] == Max_Int)
            printf("0无法到达%c\n", G.vex[i]);
        else
            printf("0到%c的权值为：%d\n", G.vex[i], D[i]);
    }
    return 0;
}

主函数首先创建图，然后调用迪杰斯特拉算法计算从顶点0到其他所有顶点的最短路径，并输出结果。