为什么80%的码农都做不了架构师?>>>
#include <iostream>
using namespace std;
//最多的顶点数
#define MaxNode 30
#define MaxCost 1000 //没有边无穷大
int cost[MaxNode][MaxCost] ; //带权邻接矩阵
int dist[MaxNode] ; //顶点间的最短距离
int n =6;
void shortdjs(int v0){
int s[MaxNode]; //顶点距离
int mindis , dis , i,j,u;
for(i=1; i<= n ; i++){
dist[i]=cost[v0][i];//将2顶点的距离放入dist并将s初始化为0
s[i]=0;
}
s[v0]=1;
for(i=1; i<=n ; i++){
mindis=MaxCost;
for(j=1; j<=n ; j++){
if(s[j]==0 && dist[j]<mindis){//查找到权值最小的并记录顶点u
u=j;
mindis=dist[j];
}
}
}
s[u]=1;
for(j=1 ; j <= n ;j++){
if(s[j]==0){//剩下的没有确定的权值的顶点
dis=dist[u] + cost[u][j];
dist[j]=(dist[j]<dis ) ? dist[j] : dis;//计算并确定最小的权值
}
}
}
void dispath(int v0){
int i;
printf("\n顶点%d到顶点的最短路径长度:\n",v0);
for(i=1;i<= n ; i++){
printf("(V%d->V%d)",v0,i);
if(dist[i] == MaxCost){
printf("无路径\n");
}else{
printf("%d\n",dist[i]);
}
}
}
void main(){
int i,j,v0=2;
for(i=1; i<=n ; i++){
for(j=1; j<=n ;j++){
cost[i][j]=MaxCost;//初始化数据为1000
}
}
for(i=1; i <= n ;i++)
cost[i][i]=0; //自己到自己依次初始化为0
cost[1][2]=50;cost[1][3]=10;
cost[1][5]=45;cost[2][3]=15;
cost[2][4]=50;cost[2][5]=10;
cost[3][1]=20;cost[3][4]=15;
cost[4][1]=20;cost[4][5]=35;
cost[5][4]=30;cost[6][4]=3;//初始化顶点的权值
shortdjs(v0);
dispath(v0);
}
测试结果:
顶点2到顶点的最短路径长度:
(V2->V1)无路径
(V2->V2)0
(V2->V3)15
(V2->V4)40
(V2->V5)10
(V2->V6)无路径