C语言prim算法求图的最短路径，给出具体路径

Prim算法是一种用于求解加权无向连通图的最小生成树的算法，它不能用于求解图的最短路径。

如果你想求解图的最短路径，可以使用Dijkstra算法或者Bellman-Ford算法。这里以Dijkstra算法为例，具体路径如下：

假设我们有一个加权无向连通图，其中每条边都有一个权值。我们想要求解从起点s到终点t的最短路径。

1. 初始化

首先，我们将起点s的距离设置为0，将所有其他节点的距离设置为无穷大。同时，我们把所有节点标记为未访问。

2. 访问节点

接下来，我们找到距离起点s最近的未访问节点v，并将其标记为已访问。

3. 更新距离

然后，我们遍历节点v的所有邻居节点，并更新它们的距离。如果从起点s到v再到邻居节点u的距离比当前已知的距离更短，我们就将它们的距离更新为这个更短的距离。

4. 重复步骤2和步骤3

重复执行步骤2和步骤3，直到我们访问了终点t或者所有节点都被访问了。这时，从起点s到终点t的最短路径就被找到了。

具体路径可能因为图的不同而不同，但是一般来说，Dijkstra算法会找到一条从起点s到终点t的最短路径，并且该路径是不经过任何中间节点的最短路径。如果有多条最短路径，Dijkstra算法只会找到其中一条。

相关问题

利用c++代码具体实现关于有向有权图中寻求最短路径prim算法

我可以提供一个简单的C语言实现，如下： #include<stdio.h>
#define MAX 100
#define infinity 9999 int G[MAX][MAX],spanning[MAX][MAX],n; int prim(){
int cost[MAX][MAX];
int u,v,min_distance,distance[MAX],from[MAX];
int visited[MAX],no_of_edges,i,min_cost,j; //初始化cost[][]矩阵
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(G[i][j]==0)
cost[i][j]=infinity;
else
cost[i][j]=G[i][j];
spanning[i][j]=0;
}

//初始化访问状态,distance[]和from[]数组
distance[0]=0;
visited[0]=1; for(i=1;i<n;i++)
{
distance[i]=cost[0][i];
from[i]=0;
visited[i]=0;
} min_cost=0; //初始化最小费用
no_of_edges=n-1; //初始化边的数量 while(no_of_edges > 0)
{
//选择最小距离的节点
min_distance=infinity;
for(i=1;i<n;i++)
if(visited[i]==0&&distance[i]<min_distance)
{
v=i;
min_distance=distance[i];
}

u=from[v]; //将边加入到最小生成树中
spanning[u][v]=distance[v];
spanning[v][u]=distance[v];
no_of_edges--;
visited[v]=1; //更新最小费用
min_cost=min_cost+cost[u][v]; //更新distance[]数组
for(i=1;i<n;i++)
if(visited[i]==0&&cost[i][v]<distance[i])
{
distance[i]=cost[i][v];
from[i]=v;
}
}
return(min_cost);
} int main()
{
int i,j,total_cost;
printf("Enter no. of vertices:");
scanf("%d",&n);

printf("\nEnter the adjacency matrix:\n");

for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&G[i][j]);

total_cost=prim();
printf("\nspanning tree matrix:\n");

for(i=0;i<n;i++)
{
printf("\n");
for(j=0;j<n;j++)
printf("%d\t",spanning[i][j]);
}

printf("\n\nTotal cost of spanning tree=%d",total_cost);
return 0;
}

构建图的最小生成树或求最短路径C语言

最小生成树算法：

使用Prim算法实现：

#include <stdio.h>
#include <stdbool.h> // bool类型需要用到

#define MAX_VERTICES 100
#define INF 1000000

int num_vertices; // 图中顶点个数
int adj_matrix[MAX_VERTICES][MAX_VERTICES]; // 图的邻接矩阵

void prim(int start_vertex) {
    bool visited[MAX_VERTICES] = {false}; // 顶点是否已被访问
    int distance[MAX_VERTICES]; // 到各顶点的距离
    int parent[MAX_VERTICES]; // 生成树的父节点

    // 初始化
    for (int i = 0; i < num_vertices; i++) {
        visited[i] = false;
        distance[i] = INF;
        parent[i] = -1;
    }
    distance[start_vertex] = 0;

    for (int i = 0; i < num_vertices - 1; i++) { // 循环n-1次，构建n-1条边
        int min_distance = INF;
        int u; // 最小距离对应的顶点编号
        // 找到未被访问过的、到起点距离最短的顶点
        for (int j = 0; j < num_vertices; j++) {
            if (!visited[j] && distance[j] < min_distance) {
                min_distance = distance[j];
                u = j;
            }
        }
        visited[u] = true; // 对该顶点进行标记
        // 更新与该顶点相邻的顶点到起点的距离
        for (int v = 0; v < num_vertices; v++) {
            if (adj_matrix[u][v] != 0 && !visited[v] && adj_matrix[u][v] < distance[v]) {
                distance[v] = adj_matrix[u][v];
                parent[v] = u;
            }
        }
    }

    // 输出生成树
    printf("生成树：\n");
    for (int i = 1; i < num_vertices; i++) { // 从第二个顶点开始，依次输出每个顶点的父节点和边的权值
        printf("%d - %d (%d)\n", parent[i], i, adj_matrix[i][parent[i]]);
    }
}

int main() {
    printf("请输入图中顶点个数：");
    scanf("%d", &num_vertices);
    printf("请输入图的邻接矩阵：\n");
    for (int i = 0; i < num_vertices; i++) {
        for (int j = 0; j < num_vertices; j++) {
            scanf("%d", &adj_matrix[i][j]);
        }
    }
    printf("请输入起点编号：");
    int start_vertex;
    scanf("%d", &start_vertex);
    prim(start_vertex);
    return 0;
}

使用Kruskal算法实现：

#include <stdio.h>
#include <stdbool.h> // bool类型需要用到

#define MAX_VERTICES 100
#define INF 1000000

int num_vertices; // 图中顶点个数
int adj_matrix[MAX_VERTICES][MAX_VERTICES]; // 图的邻接矩阵

int parent[MAX_VERTICES]; // 并查集数组

// 并查集查找根节点
int find(int x) {
    while (parent[x] != -1) {
        x = parent[x];
    }
    return x;
}

void kruskal() {
    int total_weight = 0; // 最小生成树的总权值
    int edge_count = 0; // 已选取的边的数量

    // 初始化并查集
    for (int i = 0; i < num_vertices; i++) {
        parent[i] = -1;
    }

    // 对所有边按权值从小到大排序
    struct {
        int u, v, weight;
    } edges[num_vertices * num_vertices]; // 边的数组，最多有n^2条边
    int count = 0; // 实际边的数量
    for (int i = 0; i < num_vertices; i++) {
        for (int j = i + 1; j < num_vertices; j++) { // 使用邻接矩阵，只需要遍历矩阵的上三角
            if (adj_matrix[i][j] != 0) {
                edges[count].u = i;
                edges[count].v = j;
                edges[count].weight = adj_matrix[i][j];
                count++;
            }
        }
    }
    for (int i = 0; i < count - 1; i++) { // 冒泡排序
        for (int j = 0; j < count - i - 1; j++) {
            if (edges[j].weight > edges[j+1].weight) {
                struct {
                    int u, v, weight;
                } temp = edges[j];
                edges[j] = edges[j+1];
                edges[j+1] = temp;
            }
        }
    }

    // 依次选取权值最小的边，如果两个顶点不在同一个连通分量中，则加入最小生成树
    printf("生成树：\n");
    while (edge_count < num_vertices - 1) { // 已选取的边的数量小于n-1时，继续选取
        int u = edges[edge_count].u;
        int v = edges[edge_count].v;
        int weight = edges[edge_count].weight;
        int root_u = find(u);
        int root_v = find(v);
        if (root_u != root_v) { // 如果两个顶点不在同一个连通分量中
            parent[root_u] = root_v; // 合并连通分量
            printf("%d - %d (%d)\n", u, v, weight); // 输出边
            total_weight += weight; // 加上边的权值
        }
        edge_count++;
    }
    printf("最小权值和：%d\n", total_weight);
}

int main() {
    printf("请输入图中顶点个数：");
    scanf("%d", &num_vertices);
    printf("请输入图的邻接矩阵：\n");
    for (int i = 0; i < num_vertices; i++) {
        for (int j = 0; j < num_vertices; j++) {
            scanf("%d", &adj_matrix[i][j]);
        }
    }
    kruskal();
    return 0;
}

最短路径算法：

使用Dijkstra算法实现：

#include <stdio.h>
#include <stdbool.h> // bool类型需要用到

#define MAX_VERTICES 100
#define INF 1000000

int num_vertices; // 图中顶点个数
int adj_matrix[MAX_VERTICES][MAX_VERTICES]; // 图的邻接矩阵

void dijkstra(int start_vertex) {
    bool visited[MAX_VERTICES] = {false}; // 顶点是否已被访问
    int distance[MAX_VERTICES]; // 起点到各顶点的距离

    // 初始化
    for (int i = 0; i < num_vertices; i++) {
        visited[i] = false;
        distance[i] = INF;
    }
    distance[start_vertex] = 0;

    for (int i = 0; i < num_vertices; i++) { // 循环n次，每次确定一个顶点的最短路径
        int min_distance = INF;
        int u; // 最小距离对应的顶点编号
        // 找到未被访问过的、到起点距离最短的顶点
        for (int j = 0; j < num_vertices; j++) {
            if (!visited[j] && distance[j] < min_distance) {
                min_distance = distance[j];
                u = j;
            }
        }
        visited[u] = true; // 对该顶点进行标记
        // 更新与该顶点相邻的顶点到起点的距离
        for (int v = 0; v < num_vertices; v++) {
            if (adj_matrix[u][v] != 0 && !visited[v] && distance[u] + adj_matrix[u][v] < distance[v]) {
                distance[v] = distance[u] + adj_matrix[u][v];
            }
        }
    }

    // 输出到各顶点的最短路径
    printf("起点到各顶点的最短路径：\n");
    for (int i = 0; i < num_vertices; i++) {
        printf("%d -> %d: %d\n", start_vertex, i, distance[i]);
    }
}

int main() {
    printf("请输入图中顶点个数：");
    scanf("%d", &num_vertices);
    printf("请输入图的邻接矩阵：\n");
    for (int i = 0; i < num_vertices; i++) {
        for (int j = 0; j < num_vertices; j++) {
            scanf("%d", &adj_matrix[i][j]);
        }
    }
    printf("请输入起点编号：");
    int start_vertex;
    scanf("%d", &start_vertex);
    dijkstra(start_vertex);
    return 0;
}

使用Bellman-Ford算法实现：

#include <stdio.h>
#include <stdbool.h> // bool类型需要用到

#define MAX_VERTICES 100
#define INF 1000000

int num_vertices; // 图中顶点个数
int adj_matrix[MAX_VERTICES][MAX_VERTICES]; // 图的邻接矩阵

void bellman_ford(int start_vertex) {
    int distance[MAX_VERTICES]; // 起点到各顶点的距离

    // 初始化
    for (int i = 0; i < num_vertices; i++) {
        distance[i] = INF;
    }
    distance[start_vertex] = 0;

    for (int i = 0; i < num_vertices - 1; i++) { // 循环n-1次，每次松弛n-1条边
        for (int u = 0; u < num_vertices; u++) {
            for (int v = 0; v < num_vertices; v++) {
                if (adj_matrix[u][v] != 0 && distance[u] + adj_matrix[u][v] < distance[v]) {
                    distance[v] = distance[u] + adj_matrix[u][v];
                }
            }
        }
    }

    // 判断是否存在负权回路
    bool has_negative_cycle = false;
    for (int u = 0; u < num_vertices; u++) {
        for (int v = 0; v < num_vertices; v++) {
            if (adj_matrix[u][v] != 0 && distance[u] + adj_matrix[u][v] < distance[v]) {
                has_negative_cycle = true;
                break;
            }
        }
    }

    if (has_negative_cycle) {
        printf("图中存在负权回路\n");
    } else {
        // 输出到各顶点的最短路径
        printf("起点到各顶点的最短路径：\n");
        for (int i = 0; i < num_vertices; i++) {
            printf("%d -> %d: %d\n", start_vertex, i, distance[i]);
        }
    }
}

int main() {
    printf("请输入图中顶点个数：");
    scanf("%d", &num_vertices);
    printf("请输入图的邻接矩阵：\n");
    for (int i = 0; i < num_vertices; i++) {
        for (int j = 0; j < num_vertices; j++) {
            scanf("%d", &adj_matrix[i][j]);
        }
    }
    printf("请输入起点编号：");
    int start_vertex;
    scanf("%d", &start_vertex);
    bellman_ford(start_vertex);
    return 0;
}