『算法-ACM 竞赛-图论』（技巧）超级源点与超级汇点

图论–（技巧）超级源点与超级汇点

背景：给出题目，在一张图中有多个点起点，一个终点，求所有起点到终点的最短距离。

解题方法：

1.跑 N 边单源最短路，但是这样是不行的肯定超时。

2.floyd 求出所有最短路，枚举每个起点到终点的距离，这个似乎比法 1 更慢。

3.反向建边，反向跑一遍 Dijkstra，或者 SPFA，这样就能求到终点到起点的距离，在枚举最小的一个即可，时间复杂度为一遍最短路加枚举 N。

4.建立超级源点，虚拟出一个点作为源点，源点到所有起点的距离都是 0，那么这样求超级源点到终点的最短距离就是所有起点到终点的距离的最短一个，时间复杂度为一遍最短路。

题目二：给出一张图中有一个起点，有多个终点，求一个起点到所有终点的最短距离。

解题方法：

1.直接忽略 floyd

2.一遍最短路（SPFA 或 Dijkstra），枚举 N。

3.建立超级汇点，所有终点到汇点的距离为 0，一遍最短路即可的出答案。

**题目三:**给出一张图，图中有若干起点与若干终点，在所有终点到起点的距离中的最短距离。

解题方法:

1.跑若干遍最短路，找到所有最短距离，比较得出最小值

2.建立超级源点，建立超级汇点，一遍 Dijkstra 或 SPFA 即可。

通过上面我们大致知道超级源点超级汇点的建立的条件，而且通过超级源点（汇点）可以极大的减少题目的时间复杂度，在图论中用的比较多。最后我们用图的方式表示源点及汇点的建立。

图论其他知识戳这里：https://blog.csdn.net/weixin_43627118/article/category/8966760