ACM集训之四：图论 dijkstra算法 (狄克斯特拉算法)(HDU 2544 +HDU 1874)

dijkstra(狄克斯特拉)知识点

1、可以用于解决最短路问题
2、dijkstra算法在数据量比较小的情况下可以直接开邻接矩阵。
3、不能处理含有负权环的图

对dijkstra算法的理解

dijkstra算法类似广度优先算法。

每次都把周围的与目前的源点相连的点先搜一遍，更新一遍，然后看哪个点近，把它当成下一个源点继续搜，同时不断更新距离。搜完所有的点后，就得到了源点到所有的点的最短距离。

一些变量的意思

mp[i][j]=value表示图中存在由i到j的路，这条路的权值为value。读图的时候，如果题目允许两个顶点之间有多条边，那么为了得到最短距离，在存图的时候最好加上

if(mp[a][b]>c)//两个城镇之间允许有多条不同长度的路 
				mp[a][b]=mp[b][a]=c;

dis[]数组记录最短距离，这个数组在算法执行的过程中是存储着这个过程当中暂时的最短距离，直到算法执行完后，所有的最短距离才是确定并且正确的。（更新距离的时候用的贪心）

book[]数组用于标记是否搜过。
题目
HDU 2544
http://acm.hdu.edu.cn/showproblem.php?pid=2544HDU
HDU 1874
http://acm.hdu.edu.cn/showproblem.php?pid=1874

HDU 2544
代码

#include <cstdio>
#include<cstring>
typedef long long ll;
using namespace std;
const int INF=0x3f3f3f3f;
int mp[105][105];//存储图
int dis[105];//dis数组，存储估计值
int book[105];//book[i]代表这个点有没有被当做源点去搜索过，避免了重复搜索
int n,m;//顶点数，边数 
//dijkstra算法，即狄克斯特拉算法，不能用于包含负权值的 。 
void dijkstra(int u)
{
	memset(book,0,sizeof(book));//把每个点的最短距离都先设置为无穷大 
	int start=u;//从源点开始搜索
	for(int i=1;i<=n;i++)
		dis[i]=mp[start][i];//先更新一遍,没有直接与源点相连的点为INF 
	dis[1]=0;//源点，距离0 
	book[start]=1;//先标成搜过 
	for(int i=1;i<=n-1;i++)//一共搜索n-1个点，最后一个点没法再往后面搜索了，故n-1就结束 
	{
	 	int minn=INF;//这里代表的是最近点到源点的距离，start代表最近的点 
	 	for(int j=1;j<=n;j++)//对于每一个源点，都把源点后面的所有的点都搜索一遍 （这个for目的是找到下一个搜索的节点） 
	 	{
	 		if(!book[j]&&minn>dis[j])//如果处在源点后面的，目前遍历的点没有搜索过，并且距离比我们用minn存储的暂时的最短距离还要短 
	 		{
	 			minn=dis[j];//那么，就更新这个暂时的最短距离minn  
	 			start=j;//然后将这个离源点最近的点保存起来，用于搜索 
			}
		}
		book[start]=1;//接下来把这个已经确定的，离上一个源点最近的节点标记为搜索过，因为接下来要搜索它了 
		for(int j=1;j<=n;j++)//遍历所有的点，这个for用来修改最短路的值 
			if(!book[j]&&dis[j]>dis[start]+mp[start][j])
				dis[j]=dis[start]+mp[start][j];//用新的点来更新dis 
	}
	//程序跑完后，原先只是暂时的估计的最短的距离，成功都被更新为了真实的最短距离。 
} 
int  main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		if(n==0&&m==0)
			break;
		memset(mp,INF,sizeof(mp));
		for(int i=1;i<=m;i++)//边
		{
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			mp[a][b]=c;
			mp[b][a]=c;
		}
		dijkstra(1);//以1为源点进行搜索
		if(dis[n]==INF)
			printf("-10086\n");
		else
			printf("%d\n",dis[n]);	
	}
	return 0;
} 

http://acm.hdu.edu.cn/showproblem.php?pid=1874
HDU1874
代码

#include <cstdio>
#include<cstring>
typedef long long ll;
using namespace std;
const int INF=0x3f3f3f3f;
int mp[205][205];//存储图
int dis[205];//dis数组，存储距离
int vis[205];//vis[i]代表这个点有没有被当做源点去搜索过，避免了重复搜索
int n,m;//顶点数，边数 
void dijkstra(int s)
{
	memset(vis,0,sizeof(vis));
	for(int i=0;i<n;i++)
		dis[i]=mp[s][i];
	dis[s]=0;
	vis[s]=1;
	for(int i=0;i<n;i++)
	{
		int minn=INF;
		for(int j=0;j<n;j++)
			if(!vis[j]&&dis[j]<minn)//如果没有搜索过，并且距离更小 
			{
				minn=dis[j];
				s=j;
			}
		vis[s]=1;
		for(int j=0;j<n;j++)
			if(!vis[j]&&dis[j]>dis[s]+mp[s][j])
				dis[j]=dis[s]+mp[s][j];
	}
}
int main()
{
	int s,t;//起点，终点 
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(mp,INF,sizeof(mp));
		for(int i=0;i<m;i++)
		{
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			if(mp[a][b]>c)//两个城镇之间可能有多条不同长度的路 
				mp[a][b]=mp[b][a]=c;
		}
		scanf("%d%d",&s,&t);
		dijkstra(s); 
		if(dis[t]==INF)
			printf("-1\n");
		else
			printf("%d\n",dis[t]);
	}
	return 0;
}