0.x 2.Floyd算法理论基础

dddd数据结构课本

• Author：李英民 | Henry
• E-mail: li_yingmin@outlookdotcom
• $Beijing~~U~of~Posts~and~Telecom$$(BUPT~)$
• Home: https://liyingmin.wixsite.com/henry

• 快速了解我: About Me

• 转载请保留上述引用内容，谢谢配合！

这里可以用v2转接的意思是，不止有v2，而是加入了v2；相当于可以同时用v1和v2转接。这样来获得dij的最小值。
这样思考，最开始，只能用v1转接，达到了dij的最小值。这时加入了新结点v2转接，可能挑战已有最小值dij的只能是di2+d2j（其中di2和d2j都是上一轮只用v1转接时获得的最小值，同样也是此刻di2和d2j的最小值，因为允许v2转接并不影响此刻di2和d2j的值）。
注意：di2表示从vi到v2的最短路径（由上一轮循环获得），并不一定是vi直接到v2，d2j同理。好好体会这个可能挑战已有最小值。
所以比较上一轮的dij与di2+d2j的大小，来更新最短路径dij。这一轮之后，就可以获得允许用v1、v2转接的最短路径dij。
以此类推，之后一轮就会获得允许用v1、v2、v3转接的dij。
最终，获得允许使用v1~v7转接的dij，即所有结点到其他结点的最短路径。

这一轮之后，就可以获得可以用v1~v7所有结点转接的最终最短路径。相当于所有vi到vj的可行路径里，最短的路径。