单源最短路径 Dijkstra算法
Dijkstra算法的策略是：假设顶点集为V，设置集合S存放已被访问的顶点，然后执行下面两个步骤n次：（n为顶点数目）
每次从集合V-S中选择与起点s的最短距离最小的一个顶点（记为u），访问并加入集合S。
之后，令顶点u作为中介点，优化起点s与所有从u能到达且未访问过的顶点v的最短距离。
实现策略
集合S可用一个bool型数组vis[]来实现，vis[i]==true表示顶点Vi已经被访问；int型数组d[]表示起点s到顶点Vi的最短距离，初始时d[s]赋值为0，其余顶点赋值一个很大的数，来表示不可达。
伪代码
// G为图，一般设成全局变量；数组d为源点到达各点的最短路径长度，s为起点 Dijkstra(G,d[],s) { for(循环n次) { u = 使d[u]最小的还未被访问的顶点的标号； 记u已被访问； for(从u出发能到达的所有顶点v) { if(v未被访问&&以u为中介点能使s到顶点v的最短距离d[v]更优){ 优化d[v]; } } } }时间复杂度
外层循环控制必须把每个结点都标记为访问，O(n)，内层循环需要枚举寻找最小的d[u]，也为O(n) 故时间复杂度O(n^2)注意：dijkstra算法只能应对所有边权都是非负数的情况，出现负边权最好使用SPFA算法。
Bellman-Ford(BF)算法
BF算法可解决单源最短路径问题，也能处理带负权边的情况。当图中存在环时，根据环中边权之和的正负，可以将环分为零环、正环和负环。显然，零环和正环不会影响最短路径的求解，同时有源点不可达的负环存在也不影响最短路径求解；当有源点可达的负环时，最短路径不存在。
Bellman-Ford算法同样设置数组d[]存放源点到各顶点的最短距离，且BF算法返回一个bool值，如果有源点可达的负环则返回false;否则返回true,此时数组d中的值就是源点到各顶点的最短距离。
算法主要思路：对图中的边进行V-1轮的操作，每轮都遍历图中的所有边：对每条边u->v，如果以u为中介点可以使d[v]更小，则用d[u]+weight(u,v)更新d[v]。时间复杂度：O(VE)，V顶点个数，E是边数。
伪代码
for(int i=0;i<n-1;i++)
{
for(对每条边 u->v){
if(d[u]+weight(u,v)<d[v])
d[v] = d[u] + weight(u,v);
}
}
// 检查是否存在源点可达的负环
// 只需要再对所有边进行一次遍历，看是否能继续松弛
for(每条边u->v){
if(d[u]+weight(u,v)<d[v]){
return false;
}
}
return true;SPFA
- BF算法思路简洁但复杂度确实高。我们发现，只有当某个顶点u的d[u]值改变时，从它出发的边的邻接点v的值d[v]才有可能改变。因此可以进行如下优化：建立队列，每次将队首u取出，如果d[v]>d[u]+weight(u,v)成立，即可以松弛操作，则更新d[v]，将顶点v加入队列中。这样操作直到队列为空。如此优化后的算法称为SPFA。
- 复杂度O(kE)，k为常数，E为边数。(使用数组num记录每个顶点入队的次数，如果顶点i的num[i]>=N,则说明存在源点可达的负环。)
Floyd算法 全源最短路问题
Floyd算法基于这样一个事实：如果存在顶点k,使得以k作为中介点时顶点i和顶点j的当前最短距离缩短，那么更新d[i][j] = d[i][k] + d[k][j](其中d[i][j]表示顶点i到顶点j的最短距离。
伪代码
枚举顶点k∈[1,n]
以顶点k作为中介点，枚举所有的顶点对i和j (i∈[1,n],j∈[1,n])
如果d[i][j]>d[i][k]+d[k][j]
赋值d[i][j] = d[i][k] + d[k][j]
- 可以看到，Floyd算法的思想异常简洁。时间复杂度O(n^3)
例1
朴素dijkstra O(n^2)
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int N, int K) {
vector<vector<long long>>graph(N+1,vector<long long>(N+1,INT_MAX));
// 构建图
for(int i=1;i<=N;++i) graph[i][i] = 0;
for(auto it:times)
{
graph[it[0]][it[1]] = it[2];
}
// 记录各顶点是否访问过
vector<bool>visit(N+1,false);
// 源点到各顶点的距离
vector<long long>d(N+1,INT_MAX);
// 初始化
d[K] = 0;
// 循环N次
for(int i=1;i<=N;++i)
{
int u = -1;
long long min_dis = INT_MAX;
// 找到未访问顶点中离源点最近的
for(int j=1;j<=N;++j)
{
/////// 第一次必定选中从源点s出发
if(!visit[j] && d[j]<min_dis)
{
min_dis = d[j];
u = j;
}
}
if(u==-1) break;
visit[u] = true;
for(int k=1;k<=N;k++)
{
// 以u作为中介点可以到达的所有点,如果以u为中介可以使d[k]更优，则更新
if((graph[u][k]!=INT_MAX) && (!visit[k]) && (d[k]>d[u]+graph[u][k]))
d[k] = d[u] + graph[u][k];
}
}
int ans = INT_MIN;
for(int i=1;i<=N;++i)
{
if(d[i]==INT_MAX) return -1;
ans = max(ans,(int)d[i]);
}
return ans;
}
};堆优化 dijkstra O(E*log(V))
class Solution {
public:
struct cmp{
bool operator()(pair<int,int>& a,pair<int,int>& b)
{
return a.first > b.first; // 小顶堆
}
};
int networkDelayTime(vector<vector<int>>& times, int N, int K) {
// first是距离，second是目标点
priority_queue<pair<int,int>,vector<pair<int,int>>,cmp>pq;
// 源点到各顶点的距离
vector<int>d(N+1,INT_MAX);
d[K] = 0;
// 起点入队
pq.push(make_pair(0,K));
while(!pq.empty())
{
// it为连接已访问点和未访问点的最小边
auto it = pq.top(); pq.pop();
// 如果这条边的长度已经比最短路径还大，则不可能缩短路径
// 说明这个pair保持的数据过时，最短路径值已经更新过
if(it.first>d[it.second]) continue;
for(int i=0;i<times.size();++i)
{
if(times[i][0]==it.second)
{
int v = times[i][1];
int w = times[i][2] + it.first;
if(d[v]>w)
{
pq.push(make_pair(w,v));
d[v] = w;
}
}
}
}
int ans = INT_MIN;
for(int i=1;i<=N;++i)
{
if(d[i]==INT_MAX) return -1;
ans = max(ans,d[i]);
}
return ans;
}
};BF算法
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int N, int K) {
vector<int>d(N+1,INT_MAX);
d[K] = 0;
// Bellman-Ford
// 执行N-1轮
for(int i=1;i<N;++i)
{
// 每一轮遍历所有边
for(auto it:times)
{
int u = it[0];
int v = it[1];
int w = it[2];
// 松弛
if(d[u]!=INT_MAX && d[u]+w<d[v])
d[v] = d[u] + w;
}
}
int ans = INT_MIN;
for(int i=1;i<=N;++i)
{
if(d[i]==INT_MAX) return -1;
ans = max(ans,d[i]);
}
return ans;
}
};
SPFA
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int N, int K) {
// 建图
vector<vector<int>>graph(N+1,vector<int>(N+1,INT_MAX));
for(int i=1;i<=N;++i) graph[i][i] = 0;
for(auto e : times) graph[e[0]][e[1]] = e[2];
vector<int>d(N+1,INT_MAX);
// SPFA
queue<int>q;
// 顶点入队
d[K] = 0;
q.push(K);
while(!q.empty())
{
int p = q.front();
q.pop();
for(int i=1;i<=N;++i)
{
if(d[p]!=INT_MAX && graph[p][i]!=INT_MAX && d[p] + graph[p][i] < d[i])
{
// 松弛
d[i] = d[p] + graph[p][i];
// 距离有更新的顶点入队
q.push(i);
}
}
}
int ans = INT_MIN;
for(int i=1;i<=N;++i)
{
if(d[i]==INT_MAX) return -1;
ans = max(ans,d[i]);
}
return ans;
}
};Floyd算法
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int N, int K) {
// 建图
vector<vector<int>>graph(N+1,vector<int>(N+1,INT_MAX));
for(int i=1;i<=N;++i) graph[i][i] = 0;
for(auto e : times) graph[e[0]][e[1]] = e[2];
// Floyd
// 枚举所有顶点依次作为中介点
for(int k=1;k<=N;++k)
{
// 看点对i,j能否以k作中介进行松弛
for(int i=1;i<=N;++i)
for(int j=1;j<=N;++j)
{
if(graph[i][k]!=INT_MAX && graph[k][j]!=INT_MAX && graph[i][k] + graph[k][j] < graph[i][j])
graph[i][j] = graph[i][k] + graph[k][j];
}
}
int ans = INT_MIN;
for(int i=1;i<=N;++i)
{
if(graph[K][i]==INT_MAX) return -1;
ans = max(ans,graph[K][i]);
}
return ans;
}
};
京公网安备 11010502036488号