最短路径—Dijkstra算法和Floyd算法.docx

最短路径一Dijkstra算法和Floyd算法
Dijkstra 算法

Dijkst ra（迪杰斯特拉）算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点 是以起始点为中心向外层层扩展，直到C=3 j
A 亡 f B=5
以B抑中间点，从离TC T佔漆黑短 瞬开赂携
V= <3h 氐 F>
A ->C ->E ->D =10( It上面第二步的丸一>匚一>片6要桧) 此时到b税值更改脊A "™ C ―* &=6
h ->C ->B TH；柚U中的顼点=00
叢现X ->C TD=&权蓿先轴短
4
逸入「此时£s=a X B>
止阿愈路逐A TM ■ k -AC=3 "
AT匚> 扎
“ D为中闾直’馭山T匚TE这靈摄短齬径 开葩找
11= <E> F>
AT匚TDTE =^(.址上面第二涉的代TCTE h墓底3 此时到E飒值更改対止TCTE =7
bf匚FDFF羽
发现ATCTE h祝值資屋短
£
谨入E』此时E= g匚乩忆E>
止IM坍短路径A TEJ , A ->C=3 i
匚TB二丢「k —>C ^D=6
匚f E =T
lil e沛申间点，以a ->c ->e =r达蜃最無 歸轻刑找
U= <J>
ATCTETF =12(比上面第四步的丸*匚TUTF =9 娶长，此时到F权値更改対亢TCTDTF -9 養现此TCTD宀F勻枚題対電短
e
选入F*止的駅5 :乩肚氐F>
止->A-0 i ^-)C=3>
AT匚->B=5 j A->C ->D=6
A —?C TE =sT > A ― C —>D —?9
"集含已空，堂找宛毕.
Floyd算法

FloydWarshall算法(Floyd-Warshall algorithm)是解决任意两点间的最短路径的一种算法，可以正确处理 有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包oFloyd-Warshall算法的时间复杂度为0(N3)， 空间复杂度为O(N2)。
2•算法描述
1)算法思想原理:
Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路 径。从动态规划的角度看问题，我们需要为这个目标重新做一个诠释(这个诠释正是动态规划最富创造力的精华所 在)
从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j, 2是从i经过若干个节点k到j。所以， 我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k,我们检查Dis(i,k) + Dis(k,j) < Dis(i,j) 是否成立，如果成立,证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j) = Dis(i,k) + Dis(k,)， 这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i至叮的最短路径的距离。
2).算法描述：
从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。
对于每一对顶点u和v,看看是否存在一个顶点w使得从u到w再到v比己知的路径更短。如果 是更新它。
3).FIoyd算法过程矩阵的计算----十字交叉法
方法：