0 前言

• 最短路径问题、最短路径权重、最短路径
  
• 最短路径的几个变体
  
• 最短路径的子路径也是最短路径
  
• 最短路径中没有环路
  
• 前驱子图
  
• 松弛操作
  
  
• 最短路径和松弛操作的性质
  

1 Bellman-Ford算法

1.1 介绍

• 解决单源最短路径问题，权重可以为负，可以有回路。
  
  
  

1.2 伪代码

BellmanFord(G, w, s)

InitializeSingleSource(G, s)
for i=1 to |G.v|-1
	for each edge(u, v) \in G.E
		Relax(u, v, w)
for each edge(u, v)\in G.E
	if v.d > u.d+w(u, v)
		return FALSE
return TRUE

1.3 cpp实现

#include<iostream>  
#include<cstdio>  
using namespace std;  
#define MAX 0x3f3f3f3f  
#define N 1010  

int nodenum, edgenum, original; //点，边，起点  
typedef struct Edge //边  
{  
    int u, v;  
    int cost;  
}Edge;  
   
Edge edge[N];  
int dis[N], pre[N];  
   
bool Bellman_Ford(){  
    for(int i = 1; i <= nodenum; ++i) //初始化  
        dis[i] = (i == original ? 0 : MAX);  
    for(int i = 1; i <= nodenum - 1; ++i)  
        for(int j = 1; j <= edgenum; ++j)  
            if(dis[edge[j].v] > dis[edge[j].u] + edge[j].cost) //松弛
            {  
                dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;  
                pre[edge[j].v] = edge[j].u;  
            }  
    bool flag = 1; //判断是否含有负权回路  
    for(int i = 1; i <= edgenum; ++i)  
        if(dis[edge[i].v] > dis[edge[i].u] + edge[i].cost)  
        {  
            flag = 0;  
            break;  
        }  
    return flag;  
}  

void print_path(int root) //打印最短路的路径（反向）  
{  
    while(root != pre[root]) //前驱  
    {  
        printf("%d-->", root);  
        root = pre[root];  
    }  
    if(root == pre[root])  
        printf("%d\n", root);  
}  


int main(){  
    scanf("%d%d%d", &nodenum, &edgenum, &original);  
    pre[original] = original;  
    for(int i = 1; i <= edgenum; ++i){  
        scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].cost);  
    }  
    if(Bellman_Ford())  
        for(int i = 1; i <= nodenum; ++i) //每个点最短路  
        {  
            printf("%d\n", dis[i]);  
            printf("Path:");  
            print_path(i);  
        }  
    else  
        printf("have negative circle\n");  
    return 0;  

}  

2 有向无环图中的单源最短路径问题

2.1 介绍

• 有向无环图
  
• 证明
  
• 拓展：PERT图
  

2.2 伪代码

DagShortestPaths(G, w, s)

topologically sort the vertices of G
InitializeSingleSource(G, s)
for each vertex u, taken in topologically sorted order
	for eache vertex v\in G.Adj[u]
		Relax(u, v, w)

2.3 cpp实现

#include <bits/stdc++.h>  
using namespace std;  
  
#define MAX_VERTICES 10010  // 定义图的最大结点数  
#define MAX_EDGE 10010       // 定义图的最大边数  
  
typedef struct edge{       // 定义边结点类型  
    long long adjvex;  
    long long weight;  
    struct edge *next;  
}ELink;  
typedef struct ver{       // 定义顶点结点类型  
    long long vertex, id, d, last;  
    ELink* link;  
}VLink;  
  
// 定义图的结构  
VLink G[MAX_VERTICES];  
  
void InitializeSingleSource(long long n, long long  s);  
void Relax(long long  u, long long v, ELink* edge);  
int main() {  
    int t;  
    scanf("%d", &t);  
    while(t--){  
  
        int n, m, s;  
        scanf("%d%d%d", &n, &m, &s);  
  
        // 读入  
        for(int i=0; i<m; i++){  
            long long u, v, w;  
            scanf("%lld%lld%lld", &u, &v, &w);  
            ELink* e = (ELink*) malloc(sizeof (ELink));  
            e->adjvex = v, e->weight = w, e->next = nullptr;  
            if(G[u].link == nullptr){  
                G[u].link = e;  
            }else{  
                e->next = G[u].link;  
                G[u].link = e;  
            }  
        }  
  
        // 拓扑排序  
        queue<long long > q;       //队列  
        for (int i = 1; i <= n; i++) {  
            if (G[i].id == 0)  
                q.push(i);        //把入度为0的点入队  
        }  
        vector<long long > ans;           //数组保存结果  
        while (!q.empty()) {  
            int x = q.front();         //出队  
            q.pop();  
            ans.push_back(x);  
            ELink* edge = G[x].link;  
            while (edge != nullptr) {  
                G[edge->adjvex].id--;  
                if (G[edge->adjvex].id == 0) //把入度为0的点入队  
                    q.push(edge->adjvex);  
                edge = edge->next;  
            }  
        }  
  
        InitializeSingleSource(n, s);  
        // 松弛结点  
        for(long long an: ans){  
            VLink now = G[an];  
            ELink* temp = now.link;  
            while (temp != nullptr) {  
                Relax(an, temp->adjvex, temp);  
                temp = temp->next;  
            }  
        }  
  
        // 输出结果  
        for(long long an: ans){  
            printf("%lld:%lld ", an, G[an].d);  
        }  
  
    }  
    return 0;  
}  
  
void InitializeSingleSource(long long n, long long  s){  
    for(int i=1; i<=n; i++){  
        G[i].d = INT32_MAX;  
    }  
    G[s].d = 0;  
}  
  
void Relax(long long  u, long long v, ELink* edge){  
    if(G[v].d > G[u].d+edge->weight){  
        G[v].d = G[u].d+edge->weight;  
        G[v].last = u;  
    }  
}

3 Dijkstra算法

3.1 介绍

• 适用于带有非负权重的图，可以有回路
• 单源最短路径
• 时间复杂度O((V+E)*logV)

3.2 伪代码即实现步骤

• 初始化：
  • dis[]：一个数组，用于存储从源节点到每个目标节点的最短距离。初始时，源节点到自己的距离设为0，到所有其他节点的距离设为无限大。
  • vis[]：一个布尔数组，用于标记每个节点是否已被访问。初始时，所有节点都未被访问。
  • pq[]：一个优先队列，用于存储待处理的节点及其到源点的距离。优先队列按距离升序排列，以确保总是先处理当前距离最短的节点。这里使用优先级队列的目的是降低寻找距离最短节点的时间复杂度而且可以直接调库,能够保证时间复杂度是O（logN)（进行堆排序的过程）。也可以用max_element迭代寻找，只是时间复杂度会高。
• 访问起始节点：
  将起始节点（比如 'A'）的距离设为0，标记为已访问，并将其添加到优先队列中。
• 处理优先队列中的节点：
  • 从优先队列中取出一个节点（起初是起始节点）。
  • 遍历所有从该节点出发的边。对于每一条边：
    • 计算从起始节点通过当前节点到达邻接节点的总距离。
    • 如果这个总距离小于当前记录在 dis[] 中的那个邻接节点的距离，则更新 dis[] 中对应的距离，并将该邻接节点（如果尚未访问）添加到优先队列中。
• 重复直至所有节点被访问：
  继续从优先队列中取出节点并更新距离，直到队列为空，此时所有可达节点的最短距离都已找到。

3.3 cpp实现

#include <iostream>
#include <vector>
#include<queue>
 
using namespace std;
 
struct Edge {
	int to;
	int weight;
	
	Edge(int t, int w) :to(t), weight(w) {}
};
 
//graph是用邻接表表示的图
vector<int>dijkstra(const vector<vector<Edge>>& graph, int src) {
	int n = graph.size();
	//容器定义
		//储存各个顶点到src顶点的距离
	vector<int>dis(n, INT_MAX);
		//记录访问过的顶点	
	vector<bool>vis(n, false);
		//用优先级队列来处理距离最短的顶点，pair<int,int>的第一个int存储距离，第二个int存储顶点；底层用vector来存储这个队列；greater表示从小到大排
	priority_queue<pair<int, int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
	
	//src顶点到自己的距离为0
	dis[src] = 0;
	pq.push({0,src});
 
	while (!pq.empty()) {
		//v表示当前距离最短的顶点
		int v = pq.top().second; pq.pop();
		//若是访问过当前顶点则跳过
		if (vis[v])continue;
		vis[v] = true;
		//访问邻接顶点
		for (const auto&edge: graph[v]) {
			int t = edge.to;
			int w = edge.weight;
			
			if (!vis[t]&&w + dis[v] < dis[t]) {
				dis[t] = w + dis[v];
				pq.push({ dis[t],t });
			}
		}
		
	}
	return dis;
}
 
int main() {
	int n = 5;//顶点数
	vector<vector<Edge>>graph(n);
	graph[0].push_back(Edge(1, 10));
	graph[0].push_back(Edge(2, 5));
	graph[1].push_back(Edge(2, 2));
	graph[1].push_back(Edge(3, 1));
	graph[2].push_back(Edge(1, 3));
	graph[2].push_back(Edge(3, 9));
	graph[2].push_back(Edge(4, 2));
	graph[3].push_back(Edge(4, 4));
	graph[4].push_back(Edge(3, 6));
	graph[4].push_back(Edge(0, 7));
 
	vector<int>shortest_path = dijkstra(graph, 0);
	cout << shortest_path[3];//输出9
	return 0;
}