我的DIJKSTRA为什么死循环

来源：百度知道 编辑：UC知道 时间：2024/07/01 13:24:54
我的程序如下，当输入源点4时，结果是死循环
#include<iostream.h>
#define n 5

void DIJKSTRA(float C[][n],int v)
{
int i,j,k,v1,pre;
int P[n],S[n];
float D[n];
int min,max=60,inf=80;
v1=v-1;
for(i=0;i<n;i++)
{
D[i]=C[v1][i];
if(D[i]!=32767)
P[i]=v;
else
P[i]=0;
}
for(i=0;i<n;i++)
S[i]=0;
S[v1]=1;
D[v1]=0;
for(i=0;i<n-1;i++)
{
min=inf;
for(j=0;j<n;j++)

if((!S[j])&&(D[j]<min))
{
min=D[j];
k=j;
}
S[k]=1;
for(j=0;j<n;j++)
if((!S[j])&&(D[j]>D[k]+C[k][j]))
{
D[j]=D[k]+C[k][j];
P[j]=k+1;
}
}
for(i=0;i<n;i++)
{
cout<<D[i]<<" "<<i+1;//此句不输出怎么回事？
pre=P[i];
while(pre!=0)
{
cout<<"<--"<<pre;
pre=P[

别的没有原因：注意在你程序中 P[2]=P[3]=4,所以pre=4,又pre=P[4-1]=P[3]=4,就会老是执行while里的了！！！但，怎么改还要靠楼主了！

#include<iostream.h>
#define n 5

void DIJKSTRA(float C[][n],int v)
{
int i,j,k,v1,pre;
int P[n],S[n];
float D[n];
int min,max=60,inf=80;
v1=v-1;
for(i=0;i<n;i++)
{
D[i]=C[v1][i];
if(D[i]!=32767)
P[i]=v;
else
P[i]=0;
}
for(i=0;i<n;i++)
S[i]=0;
S[v1]=1;
D[v1]=0;
for(i=0;i<n-1;i++)
{
min=inf;
for(j=0;j<n;j++)

if((!S[j])&&(D[j]<min))
{
min=D[j];
k=j;
}
S[k]=1;
for(j=0;j<n;j++)
if((!S[j])&&(D[j]>D[k]+C[k][j]))
{
D[j]=D[k]+C[k][j];
P[j]=k+1;
}
}
for(i=0;i<n;i++)
{
cout<<D[i]<<" "<<i+1;//此句不输出怎么回事？ ----输出了你没看到而已
pre=P[i];
while(pre!=0)
{
cout<<"<--"&l