用迪杰斯特拉算法和普里姆算法求最短路径

迪杰斯特拉算法和普里姆算法都是求最短路径的算法，但是它们的实现方式不同。

迪杰斯特拉算法是以起始点为中心向外层层扩展，直到扩展到终点为止。具体实现步骤如下：
1. 在地点集合中，先标记起始点。
2. 存储起始点直接到其他各地点的路径和距离，选择最短的一条，假设为起始点到C点，那此时标记C，表示已经找到起始点到C点的最短路径，比较一下起始点到其他点的距离和起始点到C点再到其他点的距离，如果经过C点的路线比较短，修改起始点到其他点的路径为起始点到C点再到其他点，并及时更新其目前最短距离。
3. 重复执行第2步直到所有地点均被标记。
4. 输出结果中的起始点到终点的路径和距离。

普里姆算法是以起始点为起点，每次选择一条与当前已经选择的点集相连的边中权值最小的边，将其连接的点加入已选择的点集中，直到所有点都被加入为止。具体实现步骤如下：
1. 在地点集合中，先标记起始点。
2. 将起始点加入已选择的点集中。
3. 选择一条与当前已经选择的点集相连的边中权值最小的边，将其连接的点加入已选择的点集中。
4. 重复执行第3步直到所有点都被加入为止。
5. 输出结果中的已选择的边和权值之和。

相关问题

迪杰斯特拉算法和普里姆算法的区别

迪杰斯特拉算法和普里姆算法都是最小生成树算法，但它们的不同点在于：

- 迪杰斯特拉算法是以起点为基础，逐步扩展生成树的，它会不断选择当前距离起点最近的点加入生成树，并更新与其相邻的点的距离。而普里姆算法是以任意一个点为基础，逐步扩展生成树的，它会不断选择当前最短边所连接的点加入生成树，直到所有点都已被加入生成树。
- 迪杰斯特拉算法对于无向图和有向图都适用，但普里姆算法只适用于无向图。
- 迪杰斯特拉算法可以求一个点到其它所有点的最短路径，而普里姆算法只能求整个图的最小生成树。

C语言迪杰斯特拉算法求带权有向图最短路径

以下是C语言实现迪杰斯特拉算法求带权有向图最短路径的示例代码：

#include <stdio.h>
#include <limits.h>

#define V 6 // 图中顶点数
#define INFINITY INT_MAX // 定义正无穷

// 找到未包含在最短路径树中的距离最小的顶点
int minDistance(int dist[], int sptSet[]) {
    int min = INFINITY, min_index;
    for (int v = 0; v < V; v++) {
        if (sptSet[v] == 0 && dist[v] <= min) {
            min = dist[v];
            min_index = v;
        }
    }
    return min_index;
}

// 打印最短路径
void printSolution(int dist[]) {
    printf("Vertex \t Distance from Source\n");
    for (int i = 0; i < V; i++) {
        printf("%d \t\t %d\n", i, dist[i]);
    }
}

// 迪杰斯特拉算法
void dijkstra(int graph[V][V], int src) {
    int dist[V]; // 存储从源到各个顶点的最短距离
    int sptSet[V]; // sptSet[i]为1表示顶点i已经包含在最短路径树中

    // 初始化所有距离为正无穷，sptSet为0
    for (int i = 0; i < V; i++) {
        dist[i] = INFINITY;
        sptSet[i] = 0;
    }

    dist[src] = 0; // 源到自身的距离为0

    // 找到未包含在最短路径树中的距离最小的顶点
    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = 1; // 将该顶点加入最短路径树中

        // 更新源到未包含在最短路径树中的顶点的距离
        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && graph[u][v] && dist[u] != INFINITY && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    printSolution(dist); // 打印最短路径
}

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

    dijkstra(graph, 0); // 从顶点0开始求最短路径

    return 0;
}