dijkstra算法的应用
dijkstra算法是干什么的？
dijkstra算法是干什么的？
dijkstra算法指的是从一个顶点到其余各顶点的最短路径算法，该算法主要解决的是有权图中最短路径问题。
该算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。
dijkstra优缺点？
dijkstra优缺点 优点:O(N*N),加堆优化:O(N*logN) 缺点: 在单源最短路径问题的某些实例中,可能存在权为负的边。优点：算法简明、能得到最优解 缺点：效率低（特别是有时候不需要最优解）、运算中占用空间大。在dijkstra算法的应用过程中,某些有权图的边可能为负,也就是说,即使有权图中并不包含可以从节点到达的负权回.
Dijkstra算法在生活中的运用？
Dijkstra算法
2.1适用范围
先说结论，dijkstra只适用于无负边权的有向或无向图.
接下来的定理证明会详细阐述这些内容.
2.2基本定理的简易证明
首先，我们有一个无负边权图g ，d[i] 表示起点s到点i的最短距离.
集合A中的数i表示d[i] 已经是最小值，不可再松弛.
显而易见，d[s] = 0 ，这个值是一个常数，所以这是最小值。此时，A = {s} .
再找到一条权值最小的连接s的边{u, v, w} ，其中u = s，w 在所有u = s 的边中最小.
我们知道，图g 是无负边权图， 而d[s] = 0 这个值最小，所以不存在一条边能使得d[v] lt d[s] w (只有无负边权图满足)，
所以d[s] w 的值对于d[v] 是最小的，不可再松弛，此时，A = {s，v} .
同理，我们便可以使用这个d[v]再去更新其他点.
2.3算法流程
2.3.1基本实现
我们使用1.2中的邻接表来存图.
d[i] 表示起点s到点i的距离，这个值应该是不断变小的，所以我们把他的初值设为INF .
vis[i] 为true时表示点i 不可再松弛，我们将vis的初值设为false.
然后我们就知道，d[s] = 0 .
接着，不断如此循环：从起点开始找一个d[i] 值最小的点，满足vis[i] = false ，将vis[i] = true .
然后遍历他的所有出边，找到权值最小的{u, v, w} ，若d[v] gt d[u] w ，便更新d[v] = d[u] w .
只要所有点i 的vis[i] = true ，就会结束循环，时间复杂度应该是: O ( N 2 ) O(N^2) O(N
2
) .
code:(使用1.2邻接表存图)
(较容易，略)
1
1
2.3.2优先队列优化
2.3.1中算法的复杂度不够理想，运用在复杂的题目中有可能会TLE .
通过分析2.3.1中的算法，我们发现，找 “d[i] 值最小的点” 这个步骤可以进行优化.
可以使用优先队列，保证每次取出的队头元素的d[i] 都是最小.
每次取队头元素这个操作的时间复杂度是: O ( log 2 N ) O(\\log_2N) O(log
2
N) .
所以优先队列优化后的时间复杂度应该是: O ( M ⋅ log 2 N ) O(