图论（四）—最短路问题（Dijkstra）

一、最短路

        概念：从某个点 A 到另一个点B的最短距离（或路径）。从点 A 到 B 可能有多条路线，多种距离，求其中最短的距离和相应路径。

        最短路径分类：

        单源最短路：图中的一个点到其余各点的最短路径

        多源最短路：图中任意两点的最短路径

         框架图解：

二、朴素Dijkstra算法

        算法思想（仅限于非负权重值）：从起始点开始，使用贪心的策略，通过加点的方法，每次遍历到起始点距离最近且未被访问过的邻接节点 t ，将 t 加入到集合 S 中，直到访问过所有节点。

     通过 N 次循环确定 n 个点到起点的最短路距离 

        时间复杂度为 

        1.在没有确定最短路中的所有点（集合 S 以外）找出距离起点最近的点 t   

        2.对 t 进行标记，加入到集合中

        3.用 t 更新其他点的最短路距离

       集合 S ：已经确定最短路的点（被访问过的点）

        定义数组 dis：从起始点到某点 ( 3 号节点 ) 的最短距离（ dis[3] ）

        定义二维数组add： 

                 表示从 节点 u 到 节点 v 的距离（区分单向与双向，双向则）

      初始化：  （以节点 1 为起始点）

        若 节点 u 与 节点 v 之间没有路径，初始化为 

      核心代码：

for(int i=1;i<=n;i++)
{
	int t=-1;
	for(int j=1;j<=n;j++)   // 在没有确定最短路中的所有点找出距离最短的那个点 t 
	   if(!s[j] && (t==-1||dis[t]>dis[j]))
	    t=j;                  
	s[t]=true; // 代表 t 这个点已经确定最短路了
	for(int j=1;j<=n;j++) // 用 t 更新其他点的最短距离 
	 dis[j] = min(dis[j],dis[t]+add[t][j]);
}

样例解释：对于下图，求出节点 A 的单源最短路 

 

三、堆优化dijkstra算法

        在朴素dijkstra算法中，遍历点是通过for循环对所有节点判断一遍得出的，”对所有节点判断“这一操作消耗了更多的时间。

        算法思想：

        可以通过堆（优先队列）进行优化，堆（优先队列）存储节点和起始点到该点最短距离，堆（优先队列）按照距离自动排序，取距离最小且未被访问过的点，同通过用邻接链表（或邻接表）储存图的方法，再进行松弛操作，并将进行松弛操作的节点插入堆中。

         ①.初始化距离：数组dis 都初始化为 0x3f3f3f3f（无穷大）,并将 1 号节点插入堆中 (dis[1]=0)

         ②取出堆顶的点（当前起始点到该点距离最小），判断是否被访问过，不断弹出取堆顶，直至找到未被访问的节点，再根据邻接链表（或邻接表）拓展。

         ③进行松弛操作，把松弛的点和距离插入到堆中。

        堆优化代码：

void dij(int s)
{
	priority_queue< pair<int,int> > q;  // 利用优先队列
	q.push(make_pair(0,s));
	memset(dis,127,sizeof(dis));
	dis[s]=0;
	while(q.size())
	{
		int u=q.top().second;
		q.pop();
		if(vis[u]==1) continue;
		vis[u]=1;
		for(int i=head[u];i;i=edge[i].next) // 链式前向星
		{
			int v=edge[i].to;
			int w=edge[i].w;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				q.push(make_pair(-dis[v],v));  // 将路径以负数保存，优先队列默认大根堆
			}
		}
	}
}

关于dijkstra算法的正确性证明，参考博文：

Dijkstra贪心算法的准确性证明_为什么这种方法求下来的路径一定是最短?试分析一下它的正确性-CSDN博客

四、dijkstra算法不能用于有负权边的图

        通过上述dijkstra思想可以得出，每次松弛操作就是通过当前离起始点最近的点来更新其他点的距离，下面举例说明。

当此时通过 节点 4 更新其他节点， dijkstra 思想已经确定 dis [ 4 ] 为 起始点 到 节点 4 的最短路，显然错误。