1. 基本定义和性质

  • 定义：在一幅加权有向图中，从顶点s到顶点t的最短路径，是所有从s到t的路径中的权重最小者
  • 路径是有向的
  • 权重不一定等价于距离
  • 并不是所有顶点都是可达的，但为了简化问题，我们使用强连通图
  • 负权重会给问题带来额外的复杂性
  • 最短路径一般都是简单的，没有环
  • 最短路径不一定是唯一的，找到其中一条就行

  • 为避免歧义，假设平行边和自环不存在

    2. 其他定义

  • 最短路径树：给定一个加权有向图和一个顶点s，以s为起点的一棵最短路径树是图的一幅子图，它包含s和从s可达的所有顶点。这棵有向树的根节点为s，树的每条路径都是有向图中的一条最短路径