迪克斯屈拉最短路徑算法圖論論-免費閱讀
【正文】 在這個過程中個人又學到了不少東西，對圖論知識在實際問題中的應用又有了更深入的理解，了解算法的優(yōu)點與缺點，更是鍛煉了動手處理實際問題的思考分析能力。 cout ，最短路徑為 : 。 ++j) printf(%8d, adjacent[i][j])。 adjacent[q][p]=adjacent[p][q] = len。 cin p。 ++j) adjacent[i][j] = infinity_value。 else cout que[i] endl。 int tmp = pre_node[destination]。amp。j++) { if ((s[j]==0)amp。//source 加入集合 distance_shortest[source]=0。 //節(jié)點個數 //Dijkstra 算法函數 //n 節(jié)點個數 ， source 源節(jié)點 void Dijkstra(int n,int source,int *distance_shortest,int *pre_node,int adjacent[maxnum][maxnum]) { bool s[maxnum]。數組 distance_shortest [n]的每個元素為頂點的距離值， pre_node [n]的每個元素為從 V1 到該頂點的路徑上此頂點的前一個頂點的序號，若從 V1 到該頂點無路徑，則用 0 作為其前一個頂點序號。然后每次從第二組的頂點中選一個其距離值為最小 Vm 的加入到第一組中，每往第一組中加入一個頂點 Vm，就要對第二組中的各個頂點的距離值進行一次修正。如果，我們將各個服務器看做是一個頂點，將服務器與服務器之間的鏈接看做是一條邊，則服務器組成的網絡就是一個無向連通圖 [9]。 路：內部點不同的鏈稱為路（ path） 。 圖論的發(fā)展已有 200 多年的歷史，它發(fā)源于 18 世紀普魯士的柯尼斯堡。其次，介紹了圖論中最短路徑的問題及相關內容，介紹了計算機網絡中服務器之間存在的最短路徑問題。圖論中的圖是由若干給定的點及連接兩點的線所構成的圖形，這種圖形通常用來描述某些事物之間的某種特定關系，用點代表事物，用連接兩點的線表示相應兩個事物間具有這種關系。 本文提出了一個計算機網絡中服務器之間最短路徑的問題背景，并在迪克斯屈拉（ Dijkstra） 算法的基礎上，實現(xiàn)算法在服務器之間尋求最短路徑的程序設計。 邊權矩陣：設 G＝ V,E是 n 階加權簡單圖，規(guī)定 D=（ dij） m n 是圖的加權矩陣，即 dij＝ w（ i， j）。另外，每個頂點對應一個距離值，第一組的頂點對應的距離值就是從 V1到此頂點的最短路徑長度，第二組的頂點對應的距離值是從 V1 到此頂點的只包括第一組的頂點為中間頂點的最短路徑長度 [2]。 . G=(V,E) （ 1）此有加權圖的鄰接矩陣表示為： （ 2）對上述問題實現(xiàn)迪克斯屈拉算法的程序過程表述為： 有鄰接矩陣 adjacent表示，若〈 S1， Sj〉是圖中的弧，則 adjacent [i， j]的值等于邊上所帶的權值，否則adjacent [i， j]等于一個很大的正數 infinity_value (在 程序中用 9999 表示 )。 //存放當前節(jié)點到達源節(jié)點的最短路徑值 int pre_node[maxnum]。//將集合置為空 if (distance_shortest[i]==infinity_value) { pre_node[i]=0。 //找出還未使用的點 j 的到源的最小路徑中 distance_shortest[j]。//加入最短路徑的點 //更新 distance_shortest for ( j=1。 int o
公司管理相關推薦
鄂ICP備17016276號-1