Dijkstra

[UNICKCHENG]

Dijkstra

待更新题库

[任务] 用Dijkstra算法求单元最短路.图中不能有负权的边
[接口]
复杂度:O(n²)
输入:
    N 全局变量,图中的点数
    g 全局变量,g[i][j]表示i到j之间边的距离
输出
    dis 全局变量,dis[i]表示节点1到i的最短距离

const int maxn=1000;
int dis[maxn],g[maxn][maxn],N;
bool v[maxn];

void dijkstra()
{
	for(int i=1;i<=N;i++)dis[i]=INF;
	dis[1]=0;
	memset(v,0,sizeof(v));
	for(int i=1;i<=N;i++)
	{
		int mark=-1,midis=INF;
		for(int j=1;j<=N;j++)
		{
			if(!v[j]&&dis[j]<mindis)
			{
				mindis=dis[j];
				mark=j;
			}
		}
		v[mark]=1;
		for(int j=1;j<=N;j++)
			if(!v[j]) dis[j]=min(dis[j],dis[mark]+g[mark][j]);
	}
}

题库

ID	TITLE	CODE(C/C++)	备注
POJ1502	MPI Maelstrom