用C实现迪杰斯特拉算法

迪杰斯特拉算法是一种用于解决单源最短路径问题的经典算法。它可以在带权重的有向图中找到从一个起点到其他所有节点的最短路径。

以下是用C语言实现迪杰斯特拉算法的基本步骤：

1. 创建一个数组dist[]，用于存储从起点到每个节点的最短距离。初始化dist[]数组，将起点到自身的距离设为0，其他节点的距离设为无穷大。

2. 创建一个数组visited[]，用于标记节点是否已被访问。初始化visited[]数组，将所有节点标记为未访问。

3. 选择起点作为当前节点，并将其标记为已访问。

4. 对于当前节点的所有邻居节点，计算从起点到这些邻居节点的距离，并更新dist[]数组中的值。如果新计算得到的距离比原先的距离小，则更新dist[]数组。

5. 从未访问的节点中选择一个距离起点最近的节点作为下一个当前节点，并将其标记为已访问。

6. 重复步骤4和步骤5，直到所有节点都被访问过或者没有可选的节点。

7. 最终，dist[]数组中存储的就是从起点到每个节点的最短距离。

下面是一个简单的用C语言实现迪杰斯特拉算法的示例代码：

#include <stdio.h>
#include <stdbool.h>

#define INF 9999
#define V 6

void dijkstra(int graph[V][V], int start)
{
    int dist[V];
    bool visited[V];

    for (int i = 0; i < V; i++)
    {
        dist[i] = INF;
        visited[i] = false;
    }

    dist[start] = 0;

    for (int count = 0; count < V - 1; count++)
    {
        int minDist = INF;
        int minIndex;

        for (int v = 0; v < V; v++)
        {
            if (!visited[v] && dist[v] <= minDist)
            {
                minDist = dist[v];
                minIndex = v;
            }
        }

        int u = minIndex;
        visited[u] = true;

        for (int v = 0; v < V; v++)
        {
            if (!visited[v] && graph[u][v] && dist[u] != INF && dist[u] + graph[u][v] < dist[v])
            {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    printf("Vertex\tDistance from Start\n");
    for (int i = 0; i < V; i++)
    {
        printf("%d\t%d\n", i, dist[i]);
    }
}

int main()
{
    int graph[V][V] = {
        {0, 4, 2, 0, 0, 0},
        {4, 0, 1, 5, 0, 0},
        {2, 1, 0, 8, 10, 0},
        {0, 5, 8, 0, 2, 6},
        {0, 0, 10, 2, 0, 3},
        {0, 0, 0, 6, 3, 0}
    };

    int start = 0;

    dijkstra(graph, start);

    return 0;
}

这段代码实现了一个简单的迪杰斯特拉算法，用于计算从起点到其他节点的最短距离。你可以根据自己的需求修改图的大小和边的权重来进行测试。