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

一、最短路

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

        最短路径分类：

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

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

         框架图解：

二、朴素Dijkstra算法

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

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

        时间复杂度为 

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

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

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

       集合 S ：已经确定最短路的点（被访问过的点）                                                                               定义数组 ：从起始点到某点 ( 3 号节点 ) 的最短距离（ dis[3] ）                                                 定义二维数组：  表示从 节点 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 的单源最短路 

 

n	1	2	3	4	5
dis	0	7	3	9	5

三、堆优化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 的最短路，显然错误。