学步园

Dijkstra算法：

使用Dijkstra算法有前提条件，所有的边为正。

讲这个算法之前首先要先定义一个无穷大的量，用INF表示，而无穷大究竟是多大呢？我们知道在实际编程中，并不存在无穷大这个定义，每种数据类型都有其表示范围，而我们这里定义的无穷大，实际上是很大的整数，这个整数并不会影响到题目的其他数据。例如，题目中给定的数据为最大不超过100，而100000这个数相对于100已经很大了那么我们就可以定义无穷大INF = 100000。

定义一个dis数组，dis[i]表示i点到源点的最短距离。

定义一个used数组，用来标记点是否使用过。

算法思想：

初始化所有节点之间没有边，我们用无穷大来表示没有边。初始化dis数组为无穷大。初始化dis[star] = 0。

循环n次

{

         在所有未被标记的节点中找到dis值最小的节点x

         标记x节点

         从x节点出发，更新所有边（x，y），更新dis[y] = min{dis[y],  d[x] + map[x][y]}

}

例如，求0到5的最短距离：

初始化：

进行第一次的循环，找到了dis值最小的0节点，标记0节点，通过0节点去更新所有和0相关的节点得到：

进行第二次循环找到dis值最小的节点1，标记，通过1节点更新所有和1相关的节点得到：

如此类推：

第三次循环：

第四次循环：

dis[5] = min{dis[5],  d[3] + map[3][5]}

第五次循环：

第六次循环：

找不到了

结束循环，输出dis[5]，即0到5点的最小距离为4。

1874-畅通工程续

实现代码：

#include <iostream>
using namespace std;

const int MAXN = 200 + 10;
int map[MAXN][MAXN];
int dis[MAXN];		//保存所有点到起点的最小距离
bool used[MAXN];
const INF = 0x3ffffff;

void init(int n)
{
	for (int i = 0; i < n; i++)
	{
		dis[i] = INF;
		for (int j = 0; j < n; j++)
		{
			map[i][j] = INF;
		}
	}
	memset (used,false,sizeof(used));
}

int dijkstra(int star, int end, int n)
{
	int MinNode;		//保存最小的距离
	dis[star] = 0;
	for (int i = 0; i < n; i++)		//贪心n次
	{
		int Min = INF;
		for (int j = 0; j < n; j++)
		{
			if (!used[j] && dis[j] < Min)
			{
				Min = dis[j];
				MinNode = j;
			}
		}
		used[MinNode] = true;
		//把MinNode作为中间点，进行松弛操作
		for (int k = 0; k < n; k++)
		{
			if (!used[k] && dis[k] > dis[MinNode] + map[MinNode][k])
			{
				dis[k] = dis[MinNode] + map[MinNode][k];
			}
		}
	}
	if (!used[end])
	{
		return -1;
	}
	else
	{
		return dis[end];
	}
}

int main()
{
	int n,m;
	while(cin>>n>>m)
	{
		int a,b,c;
		init(n);
		for (int i = 0; i < m; i++)
		{
			cin>>a>>b>>c;
			if(c < map[a][b])		//考虑如果有重边，用最小的进行构造图(好坑爹啊！！)
			{
				map[a][b] = c;
				map[b][a] = c;
			}
		}
		int s,t;
		cin>>s>>t;
		cout<<dijkstra(s, t, n)<<endl;
	}
	return 0;
}