大三上的學(xué)習(xí)總結(jié)算法

1、最短路徑算法錢羽中 王碩 陳明棟 翁源 杭天夢126347585630321379172路徑簡圖背景知識背景概述最短路徑問題是圖論研究中的一個經(jīng)典算法問題， 旨在尋找圖（由結(jié)點(diǎn)和路徑組成的）中兩結(jié)點(diǎn)之間的最短路徑。 算法具體的形式包括：確定起點(diǎn)的最短路徑問題 - 即已知起始結(jié)點(diǎn)，求最短路徑的問題。確定終點(diǎn)的最短路徑問題 - 與確定起點(diǎn)的問題相反，該問題是已知終結(jié)結(jié)點(diǎn)，求最短路徑的問題。在無向圖中該問題與確定起點(diǎn)的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)的確定起點(diǎn)的問題。確定起點(diǎn)終點(diǎn)的最短路徑問題 - 即已知起點(diǎn)和終點(diǎn)，求兩結(jié)點(diǎn)之間的最短路徑。全局最短路徑問題 - 求圖中所有的最短

2、路徑背景知識解決方法用于解決最短路徑問題的算法被稱做“最短路徑算法”， 有時被簡稱作“路徑算法”。 最常用的路徑算法有：Dijkstra算法A*算法SPFA算法Bellman-Ford算法Floyd-Warshall算法Johnson算法Dijkstra算法艾茲格W迪科斯特(Edsger Wybe Dijkstra)1 提出“goto有害論”;2 提出信號量和PV原語;3 解決了“哲學(xué)家聚餐”問題;4 最短路徑算法(SPF)和銀行家算法的創(chuàng)造者;5 第一個Algol 60編譯器的設(shè)計者和實(shí)現(xiàn)者;6 THE操作系統(tǒng)的設(shè)計者和開發(fā)者;Dijkstra算法主要思想Dijkstra(迪杰斯特拉)算法是

3、典型的最短路徑路由算法，用于計算一個節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計算的節(jié)點(diǎn)很多，所以效率低。Dijkstra算法是很有代表性的最短路算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運(yùn)籌學(xué)等等。Dijkstra算法主算法實(shí)現(xiàn)該算法的實(shí)現(xiàn)過程是這樣的 初始條件： V0是初始的頂點(diǎn)（找到V0到所有其它點(diǎn)的最短路徑）；將所有的頂點(diǎn)分為兩個組或者說兩個集合， S集合：S集合內(nèi)的頂點(diǎn)是已經(jīng)找到由V0到它們之間的最短路徑了； T集合 = V S ：是那些還沒有計算最短路徑的

4、點(diǎn)。V是所有點(diǎn)。然后是按非遞減的方式將T中的頂點(diǎn)逐一的加入到S集合中。Dijkstra算法Dijkstra算法的C語言實(shí)現(xiàn)主要代碼：typedef int PathMatrixMAXMAX;typedef int ShortPathTableMAX;void ShortestPath(MGraph G, int v0, PathMatrix &P, ShortPathTable &D)/ 求圖G從v0到其余頂點(diǎn)v的最短路徑Pv和路徑長度Dv， / 如果Pvw為TRUE，則w為v0到v的最短路徑上的頂點(diǎn)。 for( v=0; vG.vexnum; v+) /初始化 finalv = FALSE;

5、 / 表示頂點(diǎn)vS Dv = G.Edgev0v; for( w=0; wG.vexnum; w+) Pvw = FALSE; if( Dv ) Pvv0 = TRUE; Pvv = TURE; Dv0 = 0; finalv0 = TRUE;Dijkstra算法的C語言實(shí)現(xiàn)主要代碼： for( i=1; iG.vexnum; i+) /主循環(huán)，每次求一個v到v0的最短路徑 min = ; for( w=0; wG.vexnum; w+) / 求當(dāng)前的最短路徑的終點(diǎn)v if( !finalw) if( Dw min ) v = w; min = Dw; finalv = TRUE; / 將頂點(diǎn)v加入S for( w=0; wG.vexnum; w+) / 更新當(dāng)前的最短路徑及長度 if( !finalw & (min+G.Ed