• 在很多时候我们关心的可能不是两个结点直接有多少条通路，而关心的是两个结点直接有没有通路，或者最短的通路

    1. 可达性的定义

    image.png

    1.1 可达性判定，只需要求出邻接矩阵的n-1次幂

    image.png

    1.2 回路判定，只需要计算到邻接矩阵的n次幂

    image.png

    2. 可达性判定定理

    2.1 可达关系的判定

    image.png

    2.1.1 例

    image.png

    2.1 可达性矩阵

    image.png

    2.2 可达性矩阵的简洁求法

    image.png

    2.2.1 例

    image.png

    3. 最短路径

    3.1 短程线及距离

    image.png

    3.2 结点间距离的判定定理

    image.png

    3.3.1 例

    image.png
    image.png
    image.png