最短路径之Dijkstra算法（邻接矩阵实现）

（一）Dijkstra算法

单源最短路径：就是从某一个顶点出发，到图中任意顶点之间的最短路径；
【算法概述】：Dijkstra算法适用于解决单源最短路径的问题。即：从源点到任意指定顶点之间的最短距离的问题；但Dijkstra算法要求所有边的权值非负。看过Prime算法的同学都知道，Dijkstra算法与Prime算法很相似，不同的就是dis数组的更新方式。Dijkstra算法用邻接矩阵存图比较方便。
【算法思想】：先用一个数组记录从源点到图中个顶点直接相连的距离，如果不直接连，就记录为无穷大，然后通过对该数组的更新，使得dis[x]表示从源点到x的最短路径；

如图：有四个顶点，6条边；求0到3直接的最短路径？由图得知是4，那么，如何用代码实现？

1.1 初始化
用邻接矩阵来存图，先进行初始化，自己到自己的距离初始化为0，到另外的顶点的距离初始化为无穷大。并将标记数组都置为0，表示所有顶点都未访问；

int mp[N][N];	//用邻接矩阵来存图；
int dis[N];		//用了记录源点到各顶点的距离；
int vis[N];		//标记顶点是否访问过；
void inin(int n)//初始化；
{
	int i,j;
	memset(vis, 0, sizeof(vis));
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			if (i == j)
				mp[i][j] = 0;
			else
				mp[i][j] = INF;
		}
	}
}

1.2 Dijkstra主体
参数st表示源点，此题是0，n是顶点个数
第一步：先用dis数组储存与0直接相连的顶点之间的距离。并标记0号顶点；然后用一个while死循环来变量所有顶点，最坏的情况就是遍历所有顶点。
第二步：就是在当前的dis数组里找一个顶点没有访问过且距离源点最近的点，记录它的顶点下标；
第三步：更新dis数组：如果x顶点没有被访问，并且0到x顶点的距离（直接或间接）大于上面dis数组最小值加上点p到x点的距离，就对dis数组更新： dis[x] = min + mp[p][x];（可以理解为：从源点直接到某点的距离大于间接到某点的距离）
第四步：重复上面的第二步和第三步；
图示：
第一步：此时的dis数组：0 5 2 7；并标记源点0；此时的vis数组：1 0 0 0

第二步：找到最小距离2，p = 2;然后标记2号结点；此时的vis数组：1 0 1 0

第三步：更新dis数组，更新后为：0 5 2 4；

第四步：重复上面的第二步和第三步，直到所有的顶点都被访问；最后dis数组为：0 5 2 4；vis数组为：1 1 1 1

最后：

完整代码实现：

#include<iostream>
using namespace std;
#define N 1000
#define INF 0x3f3f3f3f
int mp[N][N];	//用邻接矩阵来存图；
int dis[N];		//用了记录源点到各顶点的距离；
int vis[N];		//标记顶点是否访问过；
void inin(int n)//初始化；
{
	int i,j;
	memset(vis, 0, sizeof(vis));
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			if (i == j)
				mp[i][j] = 0;
			else
				mp[i][j] = INF;
		}
	}
}
void Dijkstra(int st,int n)//这里的st是源点，和prime算法中的st不同，这个不是任意的，而是根据题目要求的源点；
{
	int i, j, p;
	for (i = 0; i < n; i++)//用dis数组记录源点到与它相连接的顶点的距离；
	{
		dis[i] = mp[st][i];
	}
	vis[st] = 1;//标记刚才源点,表示已经访问；
	while (1)
	{
		p = -1;
		int min = INF;
		for (i = 0; i < n; i++)//在当前的dis距离数组中找到一个最小的路径，并将这条路到达的顶点记录；
		{
			if (vis[i] != 1 && dis[i] < min)
			{
				min = dis[i];
				p = i;
			}
		}
		vis[p] = 1;
		if (p == -1)//直到所有的顶点都已访问过，结束循环，当然，这是最坏的情况，如果在不考虑时间的情况下，可以这么写；
			break;
		for (i = 0; i < n; i++)//更新dis数组，
		{
			if (vis[i] != 1 && dis[i] > min + mp[p][i])
			{
				dis[i] = min + mp[p][i];
			}
		}
		
	}
	
}
int main()
{
	int n, m;
	int i, j;
	cin >> n >> m;//n个顶点，m条边
	inin(n);
	for (i = 0; i < m; i++)
	{
		int a, b, x;
		cin >> a >> b >> x;//a和b之间的距离是x
		mp[a][b] = x;//无向图；
		mp[b][a] = x;
	}
	int p, q;//求p到q之间的最短路径；
	cin >> p >> q;
	Dijkstra(p,n);
	cout << dis[q] << endl;
	return 0;
}

输入：
4 6
0 1 5
0 2 2
0 3 7
1 3 1
1 2 6
2 3 2
0 3
输出：
0到3的最短路径为：4
vis数组：1 1 1 1
dis数组：0 5 2 4