随笔 - 62  文章 - 96  trackbacks - 0
<2006年10月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(7)

随笔分类(66)

随笔档案(62)

文章分类(31)

文章档案(32)

友情链接

最新随笔

积分与排名

  • 积分 - 231227
  • 排名 - 106

最新评论

阅读排行榜

评论排行榜

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之路

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理