【模板】Dijkstra - 单源最短路径
当年整理得 - -
-
#define N 1002
-
#define MAX 99999
-
int edges[N][N],d[N],n;
-
-
void dijkstra(int v)
-
{
-
int i,j;
-
bool s[N]={false};
-
for(i=1;i<=n;i++)
-
d[i]=edges[v][i];
-
d[v]=0;s[v]=true;
-
for(i=1;i<n;i++)
-
{
-
int temp=MAX;
-
int u=v;
-
for(j=1;j<=n;j++)
-
if((!s[j])&&(d[j]<temp))
-
{
-
u=j;
-
temp=d[j];
-
}
-
s[u]=true;
-
for(j=1;j<=n;j++)
-
if((!s[j])&&(edges[u][j]<MAX)&&(d[u]+edges[u][j])<d[j])
-
d[j]=d[u]+edges[u][j];
-
}
-
-
}
调用时，初始结点s，目标结点e，则
dijkstra(s);
cout<<d[e]<<endl;
即可。
注意结点是从1存储到N。
不能连通时值为MAX。
评论 (0)
