超级源点与超级汇点

超级源点与超级汇点

背景1

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

方法

  1. 跑N边单源最短路,但是这样是不行的肯定超时。
  2. floyd求出所有最短路,枚举每个起点到终点的距离,这个似乎比法1更慢。
  3. 反向建边,反向跑一遍Dijkstra,或者SPFA,这样就能求到终点到起点的距离,在枚举最小的一个即可,时间复杂度为一遍最短路加枚举N。
  4. 建立超级源点,虚拟出一个点作为源点,源点到所有起点的距离都是0,那么这样求超级源点到终点的最短距离就是所有起点到终点的距离的最短一个,时间复杂度为一遍最短路。

背景2

给出一张图中有一个起点,有多个终点,求一个起点到所有终点的最短距离。

方法

  1. 直接忽略floyd
  2. 一遍最短路(SPFA或Dijkstra),枚举N。
  3. 建立超级汇点,所有终点到汇点的距离为0,一遍最短路即可的出答案。

背景3

给出一张图,图中有若干起点与若干终点,在所有终点到起点的距离中的最短距离。

方法

  1. 跑若干遍最短路,找到所有最短距离,比较得出最小值
  2. 建立超级源点,建立超级汇点,一遍Dijkstra或SPFA即可。

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

如图

如图


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!