编写C++迪杰斯特拉最短路径

迪杰斯特拉算法是一种用于求解带权有向图的单源最短路径问题的算法。下面是用 C 语言实现的迪杰斯特拉算法的示例代码。

首先，我们需要定义一个表示带权有向图的数据结构。这里我们使用邻接矩阵来表示图，定义一个结构体来存储图的信息：

#define MAX_VERTICES 100
#define INF 1000000

typedef struct GraphType {
    int n;                   // 图中顶点数
    int weight[MAX_VERTICES][MAX_VERTICES];  // 邻接矩阵
} Graph;

接下来，我们给出迪杰斯特拉算法的实现：

void dijkstra(Graph *g, int start, int distance[], int prev[]) {
    int i, j, k, min;
    int visited[MAX_VERTICES] = { 0 };  // 标记顶点是否已访问
    for (i = 0; i < g->n; i++) {
        distance[i] = g->weight[start][i];
        visited[i] = 0;
        if (distance[i] < INF) {
            prev[i] = start;
        }
    }
    distance[start] = 0;
    visited[start] = 1;

    for (i = 1; i < g->n; i++) {
        min = INF;
        for (j = 0; j < g->n; j++) {
            if (!visited[j] && distance[j] < min) {
                min = distance[j];
                k = j;
            }
        }
        visited[k] = 1;
        for (j = 0; j < g->n; j++) {
            if (!visited[j] && min + g->weight[k][j] < distance[j]) {
                distance[j] = min + g->weight[k][j];
                prev[j] = k;
            }
        }
    }
}

该函数的参数 `g` 是一个指向 `Graph` 结构体的指针，表示待求解的图。`start` 是起点的索引，`distance` 数组保存每个顶点到起点的最短距离，`prev` 数组保存每个顶点在最短路径中的前驱顶点的索引。

在函数中，首先初始化 `distance` 和 `visited` 数组。`distance` 数组中存储的是起点到每个顶点的距离，如果两个顶点之间没有边相连，则距离为无穷大（定义为 `INF`）。`visited` 数组用于标记顶点是否已经被访问过。然后将起点标记为已访问，并更新 `distance` 数组和 `prev` 数组。

接下来，使用循环来逐步确定每个顶点到起点的最短距离。在每次循环中，先找到未访问过的距离起点最近的顶点 `k`，然后标记 `k` 为已访问。遍历所有未访问过的顶点 `j`，如果从起点到 `k` 再到 `j` 的距离更短，则更新 `distance[j]` 和 `prev[j]`。

最后，我们可以使用 `distance` 数组和 `prev` 数组来获取起点到其他顶点的最短路径。以下是一个使用示例：

int main() {
    Graph g = { 6, {
        { 0, 2, 5, 1, INF, INF },
        { 2, 0, 3, 2, INF, INF },
        { 5, 3, 0, 3, 1, 5 },
        { 1, 2, 3, 0, 1, INF },
        { INF, INF, 1, 1, 0, 2 },
        { INF, INF, 5, INF, 2, 0 }
    } };
    int distance[MAX_VERTICES], prev[MAX_VERTICES];
    dijkstra(&g, 0, distance, prev);
    for (int i = 1; i < g.n; i++) {
        printf("Shortest distance from vertex 0 to vertex %d is %d\n", i, distance[i]);
    }
    return 0;
}

在该示例中，我们定义了一个有 6 个顶点的图，并调用 `dijkstra` 函数来求解起点 `0` 到其他顶点的最短距离。输出结果为：

Shortest distance from vertex 0 to vertex 1 is 2
Shortest distance from vertex 0 to vertex 2 is 5
Shortest distance from vertex 0 to vertex 3 is 1
Shortest distance from vertex 0 to vertex 4 is 2
Shortest distance from vertex 0 to vertex 5 is 4

这说明起点到其他顶点的最短距离分别为 2、5、1、2 和 4，与预期结果相符。