求解最短路问题时为什么要虚拟一个起点和终点？

虚拟一个起点和终点可以将最短路问题转化为单源最短路问题。在实际应用中，最短路问题的常见形式是从给定起点到给定终点的最短路径，但是单源最短路问题是从一个起点到所有其他点的最短路径。因此，通过虚拟一个起点和终点，可以将问题转化为单源最短路问题，使用常见的单源最短路算法（如 Dijkstra 算法、Bellman-Ford 算法等）来求解。同时，虚拟的起点和终点作为超级源和超级汇点，可以将原图变成 DAG（有向无环图），使得算法的时间复杂度更低。