”明月如霜，好风如水，清景无限 “
- 总结
总的来说，最短路径是图论的最常见的问题。即在一副有向图（无向图是特殊的有向图，不做考虑。记图中的结点数N ，而边数为 M，边长记为W）中找到其中两点的路径最短值。
壹
* 基础版dijkstra
-
复杂度 ：O(n * n)，分析可知遍历为n,更新为n。
-
特点介绍：看复杂度可以知道，此算法仅仅与结点个数有关。那么当图的边数密集，是稠密图时，将会非常适合。而对于稠密图，储存方式最好是邻接矩阵。其中dijkstra算法对应的边长权值都为正数。
-
代码关键点：
(1).定义最短路的集合，及将最短路的结点放入其中。及认为st[t] = true;
(2).从1到n遍历
(3).找到离结点1，最近的结点记为t，将放入最短路集合
(4).通过t来更新其他结点j的信息，及min(dist[j] , dist[t] + g[t][j])
- 代码
const int N = 510;
int n , m;
int g[N][N];///存的是i到j的距离
int dist[N];///存的是1到i的最短距离
/点1开始
bool st[N];
?
int dijkstra(){
memset(dist , 0x3f , sizeof(dist));//两结点无路，记为无穷大
dist[1] = 0;
///从未确定最短的点里，找到确定的最短路径
for(int i = 0 ; i < n ; ++i){
// int t = 1;//
int t = -1;
for(int j = 1 ; j <= n ; ++j){
// if(!st[j] && dist[t] > dist[j])
if(!st[j] && (t == -1 ||dist[t] > dist[j]))
t = j;
}
st[t] = true;
///更新其他点的距离
for(int j = 1 ; j < n ; ++j)
dist[j] = min(dist[j] , dist[t] + g[t][j]);
}
return (dist[n] == 0x3f3f3f3f) ? -1:dist[n];
}
贰
* 优先队列优化dijkstra
-
复杂度 ：O(m * log n)，分析可知优先队列找n次最小值复杂度为n,而更新m条边的最短距离复杂度为 m * log n。
-
特点介绍：因为发现找到离结点1，最近的结点记为t，此过程复杂度较高，因此换为小根堆（优先队列）存储，则复杂度变为O(1)，而修改其中一条边的值，复杂度为O(log n )。
-
代码关键点：和上述一样，但是因为分析算法复杂度，及为稀疏图时（边数m小），则算法复杂度低，图的存储方式用邻接链表。注意小根堆的定义方式：priority_queue<PAI , vector , greater> heap;PAI表示的是<1到结点t的距离，结点t>
记得在入队时，先将dist[j]更新，再入队
- 代码
typedef pair<int , int> PAI;
const int N = 510;
int n , m;
int e[N] , ne[N] , h[N] , w[N], idx;///存的是i到j的距离
int dist[N];///存的是1到i的最短距离，
/点1开始
bool st[N];/有点搞不懂这个s集合
/邻接链表的存储，记得存储边长w
void add(int a, int b , int c){
e[idx] = b ;///头插b
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
?
int dijkstra(){
memset(dist , 0x3f , sizeof(dist));
dist[1] = 0;
?
priority_queue<PAI , vector<PAI> , greater<PAI>> heap;
heap.push({0 , 1});
///从未确定最短的点里，找到确定的最短路径
while(!heap.empty()){
auto t = heap.top();
heap.pop();
int distance = t.first , vec = t.second;
///即必须是t
///思考这里的st[vec]
if(st[vec]) continue;//是否可以,以下放在if(!st[vec])中
// if(!st[vec])
for(int i = h[vec] ; i != -1 ; i = ne[i]){
int j = e[i];//重点理解w[i]
if(dist[j] > distance + w[i]) {
dist[j] = distance + w[i];
heap.push({dist[j] , j});
}
}
}
return (dist[n] == 0x3f3f3f3f) ? -1:dist[n];
}
叁
* Bellman-Ford算法
-
复杂度 ：O(m * k)，遍历为m（准确为k）次，边数为m， 因此复杂度为m * k。
-
特点介绍：当图中有负权边时，可以使用。但是最大的优势是可以限制边的数量，及找结点n到结点1在最多经过k条边的情况下的最短距离。其中因为边的存储可以是结构体，定义边的三个属性起点a,终点b,权值w。如果限制最大边数k，那么必须保证在更新结点b的距离时，保证结点a的距离是上一轮的，即：
dist[b] = min(dist[b] , backup[a] + w);
- 代码：
const int N = 510 , M = 10010;
int n , m , k;///k是什莫意思呢限制k条边
存储方式是struct
int dist[N] , backup[N];///backup是什么作用呢
?
struct Edge
{
int a,b,w;
}edge[M];
?
?
int bellman_ford(){
memset(dist , 0x3f , sizeof(dist));
dist[1] = 0;
for(int i = 0 ; i < k ;++i){///最多处理到第i条边
memcpy(backup , dist , sizeof(dist));//缓冲,记住上一次循环得结果,
for(int j = 0 ; j < m ; ++j){//边
int a = edge[j].a , b = edge[j].b , w = edge[j].w;
//dist[b] = min(dist[b] , dist[a] + w);
dist[b] = min(dist[b] , backup[a] + w);
}
}
return dist[n];
}
?
- 代码关键点：即使有负环，某些点最短路也不是-∞,有k条边数限制:
肆
* SPFA算法
-
复杂度 ：O(m * n)，n个结点，边数为m， 因此复杂度最多m * n，最少m。
-
特点介绍：不能有负环，负环后的结点最短路为-∞，允许有负权值的边，主要根据bellman-ford的距离更新，
dist[b] = min(dist[b] , backup[a] + w);
-
发现b结点的距离更新和a结点有关，或者说dist[a]变小，dist[b]才会变小，有单调关系，先进先出可用队列。注意j = e[i];而w[i]表示i 到 j 的距离。st[j]表示结点j是否入队。
-
代码：
const int N = 510;
int n , m;
int e[N] , ne[N] , h[N] , w[N], idx;///存的是i到j的距离
int dist[N];///存的是1到i的最短距离，尽量最终
/点1开始
bool st[N];/有点搞不懂这个s集合
?
void add(int a, int b , int c){
e[idx] = b ;///头插b
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
?
int spfa(){
memset(dist , 0x3f , sizeof(dist));
dist[1] = 0;
queue<int> q;
q.push(1);///点数
st[1] = true;
?
while(q.size()){///结点
int t = q.front();
q.pop();
st[t] = false;
?
for(int i = h[t] ; i != -1 ; i = ne[i]){///边
int j = e[i];
if(dist[j] > dist[t] + w[i]){
dist[j] = dist[t] + w[i];
if (!st[j]) {
q.push(j);
st[j] = true;
}
}
}
}
return (dist[n] == 0x3f3f3f3f) ? -1:dist[n];
}
肆
* Floyd算法
-
复杂度 ：O(n * n * n)，n个结点，从i 到 j经过点k，注意点K在外循环。
-
特点介绍：很暴力，n^3。简单粗暴，注意初始化，i == j 时d[i][j] = 0。其中设置最大值可以从字节设置0x3f，换成较大的数 1e9。
-
代码：
const int N = 1010;
const int INF = 1e9;
?
int d[N][N]; //d[a][b]表示a到b的最短距离
int n , m;
?
void print_d(){
cout<<"d = "<<endl;
for(int i = 1 ; i <= n ; ++i){
for(int j = 1 ; j <= n ; ++j){
cout<<d[i][j]<<" ";
}
cout<<endl;
}
}
void init_floyd(){
for(int i = 1 ; i <= n ; ++i)
for(int j = 1 ; j <= n ; ++j)
d[i][j] = (i == j) ? 0 : INF;
print_d();
}
int floyd(){
for(int k = 1 ; k <= n ; ++k)
for(int i = 1 ; i <= n ; ++i)
for(int j = 1 ; j <= n ; ++j)
d[i][j] = min(d[i][j] , d[i][k] +d[k][j]);
return d[1][n];
}
源码点击阅读原文，记得点赞关注。
END
作者：不爱跑马的影迷不是好程序猿
喜欢的话请关注点赞👇 👇👇 👇
公众号 ： 文远的学习笔记
爱上层楼，浅斟低唱；酒醒何处，浮生若梦。
壹句： “C 艹 mother fucker \n”