d[i]用来保存起始点beg到点i的最短路径。
c[i][j]为边<i,j>的权。
如果边<i,j>不存在,则置c[i][j]=INF。
path[i]用来保存最短路径中点i的前一个顶点。
#include<cstdio>
const int MAX = 10000;
const int INF = 1000000;
int d[MAX];
int c[MAX][MAX];
bool flag[MAX];
//int path[MAX];
int Dijkstra(int beg, int n)
{
int i, j, u, tmp;
for(i = 1; i <= n; i++)
{
d[i] = c[beg][i];
flag[i] = false;
/*if(d[i] == INF)
path[i] = 0;
else
path[i] = beg;*/
}
d[beg] = 0; flag[beg] = true;
for(i = 1; i <= n; i++)
{
tmp = INF; u = beg;
for(j = 1; j <=n; j++)
{
if(!flag[j] && d[j] < tmp)
{
u = j;
tmp = d[j];
}
}
flag[u] = true;
for(j = 1; j <= n; j++)
{
if(!flag[j] && c[u][j] < INF)
{
if(d[u] + c[u][j] < d[j])
d[j] = d[u] + c[u][j];
//path[j] = u;
}
}
}
return 0;
}
int main()
{
return 0;
}
posted on 2006-10-10 00:22
beyonlin 阅读(3762)
评论(0) 编辑 收藏 引用 所属分类:
acm之路