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

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

引用

CSDN

1.

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;
            }
        }
    }
}

算法的主要步骤包括：

1. 初始化：将所有顶点标记为未访问，将源点到其他顶点的初始距离设置为邻接矩阵中的值，如果存在边则设置为边的权值，否则设置为无穷大。
2. 选择当前未访问顶点中距离源点最近的顶点，标记为已访问。
3. 更新从源点到其他未访问顶点的距离，如果通过当前顶点可以得到更短的路径，则更新距离和路径信息。
4. 重复步骤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到其他所有顶点的最短路径，并输出结果。

总结

迪杰斯特拉算法通过维护一个已确定最短路径的顶点集合和一个未确定最短路径的顶点集合，逐步更新最短路径信息，最终得到从源点到所有其他顶点的最短路径。这个算法在实际应用中非常广泛，例如在网络路由、地图导航等领域都有重要的应用价值。