2017华为软挑Dijkstra算法代码

虽然实现了，然俄并没有什么卵用，因为不会用，也用不上Dijkstra算法

//输出各条最短路径
void ppth(int path[],int i,int v0)  
{
int k;

k=path[i];
if(k==v0)
return;
ppth(path,k,v0);
printf("%d→ ",k);
}

//由dist计算最短路径
void DisPath(int dist[],int path[],int s[],int n,int v0)  
{
int i;
/*printf(" dist:");
for(i=0;i<n;i++)
if(dist[i]!=MAXPrice)
printf("%7d",dist[i]);
else
    printf("\t∞");
printf("\n");*/

for(i=0;i<G.connode_num;i++)
{
if(G.Con_Need[i].con_linkID != v0)
if((s[G.Con_Need[i].con_linkID]==1) && (dist[G.Con_Need[i].con_linkID]<MAXPrice))
{
printf("%d→ %d的最短路径长度为:%d  路径为:",v0,G.Con_Need[i].con_linkID,dist[G.Con_Need[i].con_linkID]);
printf("%d→ ",v0);
ppth(path,G.Con_Need[i].con_linkID,v0);
printf("%d\n",G.Con_Need[i].con_linkID);
}
else
printf("%d→%d不存在路径\n",v0,G.Con_Need[i].con_linkID);
}
}

//Dijkstra算法求最短路径和最短路径长度
void Dijkstra(int v0)  //采用Dijkstra算法求从顶点v0到其余各顶点的最短路径
{
int dist[MAXnetNote],path[MAXnetNote];
int s[MAXnetNote];
int mindis,i,j,u,n=G.netnode_num;
for(i=0; i<n; i++)
{
dist[i]=G.Link_supply[v0][i].band_price;
s[i]=0;
if(G.Link_supply[v0][i].band_price != MAXPrice)
path[i]=v0;
else
path[i]=-1;
}
s[v0]=1;
path[v0]=0;
while(true)
{
mindis=MAXPrice;
u=-1;
for(j=0; j<G.netnode_num; j++)
{
if(s[j]==0 && dist[j]<mindis)
{
u=j;
mindis=dist[j];
}
}
if(u == -1)
break;//找不到更短的路径了
s[u]=1;
for(j=0; j<G.netnode_num; j++)
{
if(!s[j])
if(G.Link_supply[u][j].band_price<MAXPrice && dist[u]+G.Link_supply[u][j].band_price<dist[j])
{
dist[j]=dist[u]+G.Link_supply[u][j].band_price;
path[j]=u;
}
}
}
printf("输出最短路径和最短路径长度为:\n");
DisPath(dist,path,s,G.netnode_num,v0);
} 


//Dijkstra算法求点到点最短路径长度
void p2p(int v0,int d0)  //采用Dijkstra算法求从顶点v0到顶点d0的最短路径
{
int dist[MAXnetNote],path[MAXnetNote];
int s[MAXnetNote];
int mindis,i,j,u,n=G.netnode_num;
for(i=0; i<n; i++)
{
dist[i]=G.Link_supply[v0][i].band_price;
s[i]=0;
if(G.Link_supply[v0][i].band_price != MAXPrice)
path[i]=v0;
else
path[i]=-1;
}
s[v0]=1;
path[v0]=0;
while(true)
{
mindis=MAXPrice;
u=-1;
for(j=0; j<G.netnode_num; j++)
{
if(s[j]==0 && dist[j]<mindis)
{
u=j;
mindis=dist[j];
}
}
if(u == -1)
break;//找不到更短的路径了
s[u]=1;
for(j=0; j<G.netnode_num; j++)
{
if(!s[j])
if(G.Link_supply[u][j].band_price<MAXPrice && dist[u]+G.Link_supply[u][j].band_price<dist[j])
{
dist[j]=dist[u]+G.Link_supply[u][j].band_price;
path[j]=u;
}
}
if(u == d0)
break;//搜索到终点d0后跳出循环
}


if(d0 != v0)
if((s[d0]==1) && (dist[d0]<MAXPrice))
{
printf("%d→ %d的最短路径长度为:%d  路径为:",v0,d0,dist[d0]);
printf("%d→ ",v0);
ppth(path,d0,v0);
printf("%d\n",d0);
}
else
printf("%d→%d不存在路径\n",v0,d0);
//DisPath(dist,path,s,G.netnode_num,v0);
}