Download presentation
Presentation is loading. Please wait.
1
Floyd-Warshall 算法构造最短路径
图论 2019年4月10日 Floyd-Warshall 算法构造最短路径 周海波 图论1.1
2
Floyd-Warshall算法原理及递归式
图论 2019年4月10日 Floyd-Warshall算法原理及递归式 2019年4月10日 图论1.1
3
图论 2019年4月10日 Floyd-Warshall算法 2019年4月10日 图论1.1
4
图论 2019年4月10日 计算前驱结点矩阵∏(n)可得最短路径 2019年4月10日 图论1.1
5
图论 2019年4月10日 1 通过D(n)构造前驱结点矩阵∏(n) 2019年4月10日 图论1.1
6
通过D(n)构造前驱结点矩阵∏(n) D(n)的第i行所诱导的子图即根节点为i的最短路径树 算法：
图论 2019年4月10日 通过D(n)构造前驱结点矩阵∏(n) D(n)的第i行所诱导的子图即根节点为i的最短路径树 算法： 𝐷 𝑖𝑘 +𝑤(𝑘,𝑗) = 𝐷 𝑖𝑗 ⇒𝑗.𝜋=𝑘 2019年4月10日 图论1.1
7
图论 2019年4月10日 2 计算D(n)的同时构造前驱结点矩阵∏(n) 2019年4月10日 图论1.1
8
图论 2019年4月10日 递归公式 2019年4月10日 图论1.1
9
图论 2019年4月10日 构造前驱结点矩阵∏(n) 2019年4月10日 图论1.1
10
图论 2019年4月10日 Wikipedia提供的算法 2019年4月10日 图论1.1
11
图论 2019年4月10日 3 使用фij(k)构造最短路径 2019年4月10日 图论1.1
12
图论 2019年4月10日 构造фij(k) фij(0)＝NIL фij(k)＝ фij(k-1) 若 dij(k-1) <= dik(k-1) + dkj(k-1) фij(k)＝ k 若 dij(k-1) > dik(k-1) + dkj(k-1) 2019年4月10日 图论1.1
13
图论 2019年4月10日 使用фij(n)构造最短路径 2019年4月10日 图论1.1
Similar presentations
