一、处理问题：负权值有向图单原点最短路径问题
二、算法描述：
假设带权值有向图中没有包含负权值环。
定义一个距离数组，dist[0...n-1]，dis[i]表示从原点到i的最短路径值
初始化数组，假设一开始在原点src出发，终点为dst，那么dist[src] = 0
遍历所有的有向边，当前遍历边（a,b)，a->b，权值为c，那么判断dist[b] > dist[a] + c，表示点从a出发到b，是否可以减少路径值，若可以则更新dist[b]的值。
三、实现，找到到达目的点的最小路径值：
int ShortestPath(int n, int src, int dst, vector<<ector<int>> edges) {
//1.定义一个距离数组dist
vector<int> dist(n, INT_MAX);
//2.初始化开始点src
dist[src] = 0;
//3.遍历所有有向边 edge[from, to, weight]
for(auto &edge : edges) {
bool any = false;//结束条件
int from = edge[0], to = edge[1];
int weight = edge[2];
//4.先判断from是可达的
if(dist[from] < INT_MAX) {
//5.从from到达to点路径更短，更新dis[to]的值
if(dist[to] < dist[from] + weight) {
dist[to] = dist[from] + weight;
any = true;
}
//6.检查结束条件，当遍历所有边都不会在减少路径时，结束。
if(!any)
break;
}
return dist[dst] == INT_MAX ? -1 : dist[dst];
}
四、找到最短路径的本身
增加一个辅助数组 p[0...n-1]，p[i]值为i节点i的前置节点
vector<int> ShortestPath(int n, int src, int dst, vector<<ector<int>> edges) {
//1.定义一个距离数组dist
vector<int> dist(n, INT_MAX);
//2.定义辅助数组p
vector<int> p(n, -1);//
//3.初始化开始点src
dist[src] = 0;
//4.遍历所有有向边 edge[from, to, weight]
for(auto &edge : edges) {
bool any = false;//结束条件
int from = edge[0], to = edge[1];
int weight = edge[2];
//5.先判断from是可达的
if(dist[from] < INT_MAX) {
//6.从from到达to点路径更短，更新dis[to]的值
if(dist[to] < dist[from] + weight) {
dist[to] = dist[from] + weight;
//7.更新辅助数组
p[to] = from;
any = true;
}
//8.检查结束条件，当遍历所有边都不会在减少路径时，结束。
if(!any)
break;
}
vector<int> path;
for(int cur = dst; cur != -1; cur = p[cur]){
path.push_back(cur);
}
reverse(path.begin(), path.end());
return path;
}
五、路径中带边数或点限制问题，限制不超过k个点，等价于不超过k+1边
我们可以在每次遍历的时候总路径长度增加1，具体做法，在遍历所有边的操作的时候，需要先对dist数组进行备份，每一次操作只会在上一次结果中进行增加，而不会出现当前操作的边，也是同一次迭代所更新的，假设本次更新的边[a, b]，如果不能确保dist[a]不是同一次迭代中更新，那么本次迭代使用边数就会超过1
具体代码实现
int ShortestPath(int n, int src, int dst, int k, vector<<ector<int>> edges) {
//1.定义一个距离数组dist
vector<int> dist(n, INT_MAX);
//2.初始化开始点src
dist[src] = 0;
//3.遍历所有有向边 edge[from, to, weight]
//增加点或边数限制
for(int limit = 0; limit < k + 1; limit++) {
vector<int> clone = dist; //每次遍历前先复制上次的结果
for(auto &edge : edges) {
bool any = false;//结束条件
int from = edge[0], to = edge[1];
int weight = edge[2];
//4.先判断from是可达的
if(clone[from] < INT_MAX) {
//5.从from到达to点路径更短，更新dis[to]的值
if(dist[to] < clone[from] + weight) {
dist[to] = clone[from] + weight;
any = true;
}
//6.检查结束条件，当遍历所有边都不会在减少路径时，结束。
if(!any)
break;
}
}
return dist[dst] == INT_MAX ? -1 : dist[dst];
}
六 Shortest Path Faster Algorithm (SPFA)
SPFA是Bellman-Ford算法的队列优化,，在Bellman-Ford算法中每次遍历所有边，并不是每条都可以进行松弛操作，SPFA主要思想是创建一个队列，将松弛节点加入到队列中，同时需要创建一个计数器来存储一个顶点被松弛多少次，检测是否存在负环，避免无限循环下去。
应用场景：求单源最短路，检测负环
具体实现
vector<vector<pair<int, int>>> adj;
bool ShortestPath(iint src) {
int n = adj.size();
//1.定义一个距离数组dist
vector<int> dist(n, INT_MAX);
//2.增加队列
queue<int> q;
//3.增加数组判断当前顶点是否存在队列中
vector<int> inqueue(n, 0);
//4.初始化开始点src
dist[src] = 0;
q.push(s);
inqueue[s] = true;
while(!q.empty()) {
int v = q.front();
q.pop();
inqueue[v] = false;
for(auto edge : adj[v]){
int to = edge.first;
int len = edge.second;
if(dist[v] + len < dist[to]) {
d[to] = d[v] + len;
if(!inqueue[to]) {
q.push(to);
inqueue[to] = true;
cnt[to]++;
if(cnt[to] > n)
return false;
}
}
}
}
return true;
}