迪克斯屈拉最短路徑算法圖論論-閱讀頁
2025-01-22 03:16本頁面
【正文】 est[source]=0。i=n。 int u=source。 for (int j=1。j++) { if ((s[j]==0)amp。(distance_shortest[j]temp)) { u=j。 } } s[u]=1。j=n。amp。 if (newdistdistance_shortest[j]) { distance_shortest[j]=newdist。 } } } } } //統(tǒng)計路徑函數(shù) void searchPath(int *pre_node,int source, int destination) { int que[maxnum]。 que[ord] = destination。 int tmp = pre_node[destination]。 ord++。 } que[ord] = source。 i=1。 else cout que[i] endl。 cin n。 // 輸入 p, q 兩端點及其路徑長度 len， num 為要統(tǒng)計的源端點 // 初始化 adjacent[][]為 infinity_value for(int i=1。 ++i) for(int j=1。 ++j) adjacent[i][j] = infinity_value。 cout例如：請輸入端點號： 1endl。 cout 請輸入 1 號端點和 2 號端點之間邊的權(quán)值： 20endl。 int judge=1。 cin p。 cout請輸入另一個端點號： 。 if (q==0) break。 姓名： 沈敬紅 學(xué)院：通信學(xué)院 學(xué)號： s140131109 7 cinlen。 adjacent[q][p]=adjacent[p][q] = len。 i=n。 for( i=1。 ++i) { for(int j=1。 ++j) printf(%8d, adjacent[i][j])。 } cout請輸入要統(tǒng)計的源節(jié)點的端點號： 。 Dijkstra(n, num, distance_shortest, pre_node, adjacent)。i=n。 cout ，最短路徑為 : 。 } } } （ 4）根據(jù)迪克斯屈拉算法得到的程序運行最后結(jié)果為： 姓名： 沈敬紅 學(xué)院：通信學(xué)院 學(xué)號： s140131109 8 圖 圖 （續(xù)） 姓名： 沈敬紅 學(xué)院：通信學(xué)院 學(xué)號： s140131109 9 從上述實例中可以看出， Dijkstra 算法是典型的最短路徑路由算法，比較適用于求出圖中 一個特定頂點到其他各頂點的最短路。但是，也可以根據(jù)以上的例子看出，該算法主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。但是，迪克斯屈拉算法無疑仍是一種優(yōu) 秀的算法，可以很好的解決實際中的最短路徑問題，并且可以和其他算法結(jié)合在一起完成更復(fù)雜的尋路過程。在這個過程中個人又學(xué)到了不少東西，對圖論知識在實際問題中的應(yīng)用又有了更深入的理解，了解算法的優(yōu)點與缺點，更是鍛煉了動手處理實際問題的思考分析能力。由于時間及個人學(xué) 習深度有限，所以在此僅介紹迪克斯屈拉算法的應(yīng)用，其他的最短路徑算法如 Floyd 算法、 Warshall 算法 等將不在敘述，希望本文對其他學(xué)習者有一定的幫
公司管理相關(guān)推薦
鄂ICP備17016276號-1