定义: 在网络中,求两个不同顶点之间的所有路径中,边的权值之和最小的那一条路径。这条路径就是两点之间的 最短路径 (Shortest Path)。 - 第一个顶点为 源点 (Source ); - 最后一个顶点为 终点 (Destination)。
根据源点的多少和是有向图还是无向图,可以分为:
单源 最短路径问题:从某固定源点出发,求其到所有其他顶点的最短路径。 (有向) 无权图 ; (有向) 有权图 。 多源 最短路径问题:求任意两顶点间的最短路径。