前言：
在竞赛中，单源最短路的话，就算是使用SPFA算法，也可能被神奇的数据卡成复杂度接近O(n * m)的，那么就GG了……所以我们主要学习Dijkstra算法（复杂度在：O(n^2)）及其堆优化（优化后复杂度在：O(n * logn)）。
分析Dijkstra算法
算法思想建模：
它的算法思想是贪心，咱们可以这样去理解：假设起点是 1号节点，我们要求出从 1号节点出发，到其他节点的最短路径，现在我们在每条邻接边上摆放多米诺骨牌，假设权重越大的边上摆放的骨牌数目越多，并且规定骨牌的倒下速度是一样的，那么也就是说骨牌数目越多倒下的时间越长，我没以起点 1号节点开始推到骨牌，很明显，骨牌少的那条边相邻的节点 u 是最先到达的，最先到达的节点与起点之间的路径必然是最短路径，如果不是最短路径，则可以找到更短的路径更先到达，然后 u 就可以算作已经确定最短路径的节点了。然后，此时倒塌的多米诺骨牌就分成了两路：一路还是从起点 1 开始继续倒塌，另一路就是从新的已经确定的节点 u 开始倒塌，然后更新已经确定最短路的节点集合A与未确定最短路径的节点集合B之间的直连路径，然后不断反复这个过程。
算法步骤分析：
以上图为例子：先设出两个集合A和B，分别为已经确定最短路径的点的集合，另一个为A集合中的节点的相邻节点，先假设以 1号节点为起点
第零步：A{1} B{2 3 4}
第一步：A{1 4} B{2 3 6}
第二步：A{1 2 4} B{5 3 6}
……
直到所有节点的都在A集合中
Dijkstra算法的核心代码：
int Dijkstra(int s, int t) {
for (int i = 0; i <= n; ++i)
dis[i] = inf;
dis[s] = 0;
for (int i = 0; i < n; ++i) {
int u = 0;
for (int j = 1; j <= n; ++j)
if (!vis[j] && (!u || dis[u] > dis[j]))
u = j;
vis[u] = true;
for (int k = 0; k < G[u].size(); k++) {
int v = G[u][k].to, w = G[u][k].cost;
if (dis[v] > dis[u] + w)
dis[v] = dis[u] + w;
}
}
return dis[t];
}
算法习题：洛谷 P1576 最小花费，也是中南大学保研上机考试的题
算法分析：
这个题乍一看不太像求最短路的问题，但是看数据规模，用DFS肯定会超时，不过神奇的是，在dengdengoj上提交是可以用DFS解决掉的（肯定是数据水，但是洛谷数据不水）
这个题说每次经过一个点，都要交手续费，那么怎么才能用最小的花费让对方收到100的金额？我们假设经过第 i 条边需要交付 zi%的手续费，也就是说，真正对方收到的是我付出的金额：MyMoney * (100 - zi)%的金额
假设要经过k条边，那么我们这个题要满足的公式就是：
MyMoney * PI((100 - zi)/100) = 100
我们要想MyMoney尽量少，那么这个 PI(100 - zi)/100 就要尽量大！
于是就变成了最大路径问题，这里注意初始化：dis[s] = 1（重要！！）
因为我们自己转给自己是不要手续费的，于是就是100/100=1，如果不这样初始化的话，由于我们是乘法，其他乘起来都是0了！而其他的点，暂时还没有连接，全都初始化为0，因为最开始，无法互通，也就是多少钱都汇不过去！
Dijkstra的AC代码：
#include <cstdio>
#include <vector>
using namespace std;
const int maxp = 2005;
struct Edge{
int to;
double cost;
Edge(int t, double c) : to(t), cost(c) {}
};
int n, m, vis[maxp], a, b;
double dis[maxp], c;
vector<Edge> G[maxp];
void Solve(int s){
dis[s] = 1.0;
for(int i = 0;i < n;++i){
int u = 0;
for(int j = 1;j <= n;++j)
if(!vis[j] && (!u || dis[j] > dis[u]))
u = j;
vis[u] = 1;
for(int k = 0;k < (int)G[u].size();++k)
if(dis[G[u][k].to] < dis[u] * G[u][k].cost)
dis[G[u][k].to] = dis[u] * G[u][k].cost;
}
}
int main(){
scanf("%d %d", &n, &m);
while(m--){
scanf("%d %d %lf", &a, &b, &c);
G[a].push_back(Edge(b, (100 - c) / 100.0));
G[b].push_back(Edge(a, (100 - c) / 100.0));
}
int s, t;
scanf("%d %d", &s, &t);
Solve(s);
printf("%.8lf", 100.0 / dis[t]);
return 0;
}
在dengdengoj上的提交：2019中南大学保研夏令营
在中南这个oj的DFS算法AC代码：
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
using namespace std;
const int maxp = 2005;
struct Edge {
int to, cost;
Edge(int t, int c) : to(t), cost(c) {}
};
int n, m, a, b, s, t, vis[maxp];
vector<Edge> G[maxp];
double ans = 9.9999999999, c;
void dfs(int p, double cnt) {
if (t == p) {
if (ans * 10000000000.0 > cnt * 10000000000.0)
ans = cnt;
return;
}
for (int i = 0; i < G[p].size(); ++i) {
int v = G[p][i].to;
if (!vis[v]) {
vis[v] = 1;
dfs(v, cnt * 100.0 / (100 - G[p][i].cost));
vis[v] = 0;
}
}
}
int main() {
scanf("%d %d", &n, &m);
while (m--) {
scanf("%d %d %lf", &a, &b, &c);
G[a].push_back(Edge(b, c));
G[b].push_back(Edge(a, c));
}
scanf("%d %d", &s, &t);
vis[s] = 1;
dfs(s, 1.0);
printf("%.8lf", ans * 100);
return 0;
}
Dijkstra算法的堆优化：
为什么要堆优化呢？？？
首先我们来分析一下Dijkstra算法的复杂度：
我们要处理N个点，每次呢要在集合B中找到最优的点作为下一个点去更新集合A，如果集合B是乱序的，那么每次更新集合A就要去遍历集合B，集合B的最坏情况是包含了N个点，所以复杂度是O(NM)
如果设想B集合是有序的，那么每次找到最优的点就只需要找第一个元素就好了，有没有高效的算法或者是数据结构呢？其实有很多，平衡树、线段树都可以，但是代码量最短的肯定是运用STL包含的模板类：优先队列就可以了！
可以达到复杂度：O(MlogN)
算法实现模板题：堆优化Dijkstra算法模板题
AC代码：
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 1e5 + 5;
struct Edge {
int to, cost;
Edge(int t, int c) : to(t), cost(c) {}
};
vector<Edge> G[maxn];
struct Node {
int N_id, N_dis;
Node(int id, int di) : N_id(id), N_dis(di) {}
bool operator< (const Node& n) const {
return N_dis > n.N_dis;
}
};
int n, m, a, b, c, s, vis[maxn], dis[maxn];
void Dijkstra() {
for (int i = 0; i <= n; ++i) dis[i] = 0x3f3f3f3f;
dis[s] = 0;
priority_queue<Node> q;
q.push(Node(s, dis[s]));
while (!q.empty()) {
Node Now = q.top(); q.pop();
if (vis[Now.N_id]) continue;
vis[Now.N_id] = 1;
for (int j = 0; j < (int)G[Now.N_id].size(); ++j) {
Edge e = G[Now.N_id][j];
if (vis[e.to]) continue;
if (dis[e.to] > e.cost + dis[Now.N_id]) {
dis[e.to] = e.cost + dis[Now.N_id];
q.push(Node(e.to, dis[e.to]));
}
}
}
}
int main() {
scanf("%d %d %d", &n, &m, &s);
while (m--) {
scanf("%d %d %d", &a, &b, &c);
G[a].push_back(Edge(b, c));
}
Dijkstra();
for (int i = 1; i <= n; ++i)
if (dis[i] < 0x3f3f3f3f)
printf("%d ", dis[i]);
else
printf("2147483647 ");
return 0;
}
从算法上进一步细致分析堆优化：
这里我们不再明确的维护一个“确定最短路径的点”的一个集合A了，而是只是去研究集合B，因为图的边有M条，每次就需要向集合B拓展M次，因为要更新B集合中的连接状态，所以我们维护集合B其实也就隐性地维护了集合A！然而我们每次都要从集合B中找到最优的状态作为下一个确定最短路的节点。这个是可以用优先队列O(1)获取，O(logn)维护的。但是这就牵扯到入队和出队的问题，我们分析一下：
最开始，连起点都在集合B中，所以最初优先队列只有一个点：起点。然后逐步扩展，在扩展的时候，就自动维护了，让最短（最优）的节点放在队首，然后依次往后。每次队首出队（意味着被确定为新的最短路径的点），那么这个队首的邻接的点的距离就需要被更新，这个更新不光是距离的更新，还要把他们入队！因为我们可以知道，节点 u 的所有邻接的节点比不邻接的节点近（没有负权边的时候一定是这样的！）所以他们必须入队作为下一波的候选节点！
优化之后，复杂度：O(M*logN)，但是用其他更高级的数据结构优化能够有更高的效率，在有些数据中，这种效率优势相当明显，等小良水平到了那个层次再和大家分享！