网络工程师考点：最短路径理解笔记

有两种算法可以实现，一种是迪杰斯特拉（Dijkstra）算法，一种是弗洛伊德（Floyd）算法。


迪杰斯特拉（Dijkstra）算法：
（给出一个出发点，可算出该出发点到所有其它点的最短距离还有具体路径）


算法过程：

一，用D[v]记录任一点v到出发点的最短距离，建立一S集合且为空，用以记录已找出最短距离的点。
二，扫描非S集中D[]值最小的节点D[w]，也就是找出下一条最短路径，把节点w加入S集中。
三，更新所有非S集中的D[]值，看看是否可通过新加入的w点让其距离更短：if(D[w]+ < D[v]) then D[v]=D[w]+;
四，跳转到（二）操作，循环（顶点数－1）次，依次找出所有顶点的最短路径。


算法理解：

先证明：下一条最短路径一定是经过S集中的顶点，或是直接到达出发点的。
也就是说下一条最短路径一定不经过S集外的顶点。
证明：如下图，v为出发点，假使w为下一条最短路径的顶点，则一定小于，否则称k为下一条最短路径，而不是w，所以 < 则 < 所以w一定通过S集中的顶点。

第一条最短路径当然是直到出发点且最短的那条，所以可以扫描初始化后的D[]直接找出最短那条，然后根据以上证明可得下一条最短路径一定是通过刚找出的那条的，由于下一条最短路径一定是通过S集的，所有不用每次都扫描所有的路径，所以只用更新有通过刚加入的顶点的路径D[]值（三操作）。再扫描出最短的D[]值，加入S集中（二操作），再更新所有D[]值，依次找出所有顶点。

弗洛伊德（Floyd）算法：
（算出所有每对顶点间的最短路径）


算法过程：

一，用D[v][w]记录每一对顶点的最短距离。
二，依次扫描每一个点，并以其为基点再遍历所有每一对顶点D[][]的值，看看是否可用过该基点让这对顶点间的距离更小。

算法理解：

最短距离有三种情况：<