利用c++代码具体实现关于有向有权图中寻求最短路径prim算法
时间: 2023-03-09 19:14:22 浏览: 78
我可以提供一个简单的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;
}