文档介绍：有两种算法可以实现,一种是迪杰斯特拉(Dijkstra)算法,一种是弗洛伊德(Floyd)算法。
迪杰斯特拉(Dijkstra)算法:
(给出一个出发点,可算出该出发点到所有其它点的最短距离还有具体路径)
算法过程:
一,用D[v]记录任一点v到出发点的最短距离,建立一S集合且为空,用以记录已找出最短距离的点。
二,扫描非S集中D[]值最小的节点D[w],也就是找出下一条最短路径,把节点w加入S集中。
三,更新所有非S集中的D[]值,看看是否可通过新加入的w点让其距离更短:if(D[w]+<w,v> < D[v]) then D[v]=D[w]+<w,v>;
四,跳转到(二)操作,循环(顶点数-1)次,依次找出所有顶点的最短路径。
算法理解:
先证明:下一条最短路径一定是经过S集中的顶点,或是直接到达出发点的。
也就是说下一条最短路径一定不经过S集外的顶点。
证明:如下图,v为出发点,假使w为下一条最短路径的顶点,则<v,u,w>一定小于<v,k>,否则称k为下一条最短路径,而不是w,所以<v,u,w> < <v,k> 则<v,u,w> < <v,k,w> 所以w一定通过S集中的顶点。
第一条最短路径当然是直到出发点且最短的那条,所以可以扫描初始化后的D[]直接找出最短那条,然后根据以上证明可得下一条最短路径一定是通过刚找出的那条的,由于下一条最短路径一定是通过S集的,所有不用每次都扫描所有的路径,所以只用更新有通过刚加入的顶点的路径D[]值(三操作)。再扫描出最短的D[]值,加入S集中(二操作),再更新所有D[]值,依次找出所有顶点。
弗洛伊德(Floyd)算法:
(算出所有每对顶点间的最短路径)
算法过程:
一,用D[v][w]记录每一对顶点的最短距离。
二,依次扫描每一个点,并以其为基点再遍历所有每一对顶点D[][]的值,看看是否可用过该基点让这对顶点间的距离更小。
算法理解:
最短距离有三种情况:
一,两点的直达距离最短。(如下图<v,x>)
二,两点间只