Shortest-PathII

Floyd algorithm 相較於Dijkstra的方法只能求出某一點到其他頂點的最短距離，如果要求出圖形中任意兩點甚至所有頂點間最短的距離，就要用Floyd演算法。 Floyd演算法定義: 原理是動態規劃。設D_i,j,k為從i到j的只以(1..k)集合中的節點為中間節點的最短路徑的長度。 ⑴ A^k[i][j]=min{A^k-1[i][j],A^k-1[i][k]+A^k-1[k][j]}，k>=1，k表示經過的頂點，A^k[i][j]為從頂點i到j經由k頂點的最短路徑。 ⑵ A^0[i][j]=COST[i]j，A^0為頂點i到j間的直通距離。 ⑶ A^[i,j]代表i到j的最短距離，即A^n是我們所要求的最短路徑成本矩陣。拿下圖舉用，用Floyd來求... Read more 29 Sep 2023 - 0 minute read

Shortest-Path

圖形最短路徑法最短路徑是圖形的經典演算法，在一個有像圖形G=(V,E)中，G每一個邊都有一個比例常數W與之對應，想要求G圖形中某一個頂點V0到其他頂點的最少總和之值，這就稱為最短路徑法。接下來介紹最短路徑的常見演算法。 Dijkstra’s algorithm Dijkstra演算法可以找到圖中最短路徑，也可以找到從節點到圖中所有其他節點的最短路徑。還可以追蹤目前已知的從每個節點之間的最短路徑，如果發現更短的路徑，則會更新這些值。一旦演算法找到來源節點和另一個節點之間的最短路徑，該節點會被標記為「已存取」並添加到路徑中，該過程持續進行，直到圖中的所有節點都以新增至路徑中，這樣就有一條來源節點連接到所有其他節點的路徑，該路徑遵循可能到達每個節點的最短路徑。 Dijkst... Read more 28 Sep 2023 - 2 minute read

GraphIII

Kruskal’s alogrithm Kruskal又稱K氏法，是將各邊依權值大小由小到大排列，接著從權值最低的邊線開始架構最小成本擴張樹，如果加入的邊線會造成迴路則捨棄不用，直到加入了n-1個邊線為止。最小成本擴張樹: ⓵ 把所有邊線的成本列出由小到大排序: 起始頂點終止頂點成本 B C 3 B D 5 A B 6 C D 7 B F ... Read more 27 Sep 2023 - 1 minute read

GraphII

擴張樹(Spanning Tree) 擴張樹又稱花費樹或值樹，一個圖形的擴張樹是以最少的邊來連結圖形中所有的頂點，且不造成循環。在樹的邊上加上一個權重值，這個圖形就成為加權圖形。擴張樹是由所有頂點及拜訪過程中經過的邊所組成，另S=(V,T)為圖形G=(V,E)中的擴張樹 1.E=T+B(T為拜訪中所經過的邊，B為拜訪過程中未經過的邊) 2.將集合B中的任一邊加入結合T中，就會造成迴圈 3.V中任兩頂點Vi與Vj，在擴張樹S中存在唯一的一條簡單路徑最小花費擴張樹(Minimum Spanning Tree) 要想知道某個點到另一個點間的路徑成本，例如從頂點1到頂點5有(1+2+4)、(1+6+4)和6這三個路徑。最小花費擴張樹就是路徑為6的擴張樹。一個加權圖形中... Read more 26 Sep 2023 - 0 minute read

Graph

圖形演算法前面也有介紹到圖形的定義，這邊會來介紹圖形的演算法。圖形的走訪前幾天的樹追蹤是拜訪樹的每一個節點一次，用的方法有前中後序法，那圖形追蹤的定義，就是G=(V,E)，我們從V開始，經由此節點相鄰的節點而去拜訪G中其他節點，稱為「圖形追蹤」。從某一個頂點V1開始，走訪可經由V1到達的頂點，接著再走訪下一個頂點直到全部的頂點走訪完畢。在走訪過程可能會重複經過某些頂點及邊線。經由圖形的走訪可以判斷該圖形是否連通，並找出連通單元及路徑。圖形走訪有兩種「先深後廣走訪」，「先廣後深走訪」。先深後廣走訪（Depth-First Search）先深後廣走訪類似前序走訪，從圖形的某一頂點開始走訪，被拜訪過的頂點就做上已拜訪的記號，接著走訪此頂點所有相鄰且未拜訪過頂點中的... Read more 25 Sep 2023 - 0 minute read

Older Newer