Dijkstra模板

/*
Dijkstra求单源最短路径
problems: hdu2544(最短路)
数组实现
时间复杂度为O(n^2)
*/
//2294223 2010-04-04 20:10:09 Accepted 2544 15MS 284K 1602 B C++ Xredman 
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAX_SIZE = 104;
const int INF = 0x03F3F3F3F;

int cost[MAX_SIZE][MAX_SIZE];//图
bool Visited[MAX_SIZE];
int lowcost[MAX_SIZE];
int path[MAX_SIZE];
int n;//图中有n个点
int m;//边数

void readin()
{
	int i, j;
	int a, b, tcost;
	for(i = 1; i <= n; i++)
	{
		for(j = 1; j <= n; j++)
			cost[i][j] = INF;
	}
	for(i = 0; i < m; i++)
	{
		scanf("%d%d%d", &a, &b, &tcost);
		cost[a][b] = cost[b][a] = tcost;
	}
}

void Dijkstra(int beg)
{
	int i, j, minx, pre;
	memset(Visited, 0, sizeof(Visited));
	Visited[beg] = true;
	for(int i = 1; i <= n; i++)
	{
		lowcost[i] = cost[beg][i];
		path[i] = beg;
	}
	lowcost[beg] = 0;
	path[beg] = -1;
	pre = beg;
	for(i = 1; i < n; i++)
	{//循环n-1次
		minx = INF;
		for(j = 1; j <= n; j++)
		{
			/*
			对没有与u相邻的点v，执行Relax(u, v),也就是如果dist[u] + w[u,v] < dist[v],
			那么把dist[v]更新为更短的距离dist[u] + w[u,v]。
			*/
			if(!Visited[j] && lowcost[pre] + cost[pre][j] < lowcost[j])
			{
				lowcost[j] = lowcost[pre] + cost[pre][j];
				path[j] = pre;
			}
		}
		for(j = 1; j <= n; j++)
		{
			if(!Visited[j] && lowcost[j] < minx)
			{//在没有扩展过的点中取一距离最小的点u，并将其状态设为已扩展。
				minx = lowcost[j];
				pre = j;
			}
		}
		Visited[pre] = true;
	}
}

int main()
{
	while(scanf("%d%d", &n, &m) && m + n)
	{
		readin();
		Dijkstra(1);
		printf("%d\n", lowcost[n]);
	}
	return 0;
}

• 相关文章
• 全局相关文章