【正文】 述 ：一開(kāi)始 第一組 只包括頂點(diǎn) V1，第二組包括其他所有頂點(diǎn)。 //存放當(dāng)前點(diǎn)的前一個(gè)節(jié)點(diǎn) int adjacent[maxnum][maxnum]。 for (int j=1。 que[ord] = destination。 ++i) for(int j=1。 姓名： 沈敬紅 學(xué)院：通信學(xué)院 學(xué)號(hào)： s140131109 7 cinlen。i=n。由于時(shí)間及個(gè)人學(xué) 習(xí)深度有限，所以在此僅介紹迪克斯屈拉算法的應(yīng)用，其他的最短路徑算法如 Floyd 算法、 Warshall 算法 等將不在敘述，希望本文對(duì)其他學(xué)習(xí)者有一定的幫助。 } cout請(qǐng)輸入要統(tǒng)計(jì)的源節(jié)點(diǎn)的端點(diǎn)號(hào)： 。 cout請(qǐng)輸入另一個(gè)端點(diǎn)號(hào)： 。 cin n。 if (newdistdistance_shortest[j]) { distance_shortest[j]=newdist。i=n。此算法起始頂點(diǎn)也可以不是 V1，起始頂點(diǎn)的序號(hào)由變量 k 給出（即從頂點(diǎn) Vk 出發(fā)）。如下圖為網(wǎng)絡(luò)服務(wù)器之間的拓?fù)鋱D： （注： S1S6 為網(wǎng)絡(luò)服務(wù)器節(jié)點(diǎn)，權(quán)值為 10ms/每單位值） 迪克斯屈拉（ Dijkstra）算法實(shí)現(xiàn) Dijkstra 算法 [1]描述： 算法基本思想 ： 一個(gè)頂點(diǎn) V1 作為源點(diǎn)，求該頂點(diǎn)到其他各頂點(diǎn)的最短路徑，迪克斯屈拉 提出了一個(gè)按路徑長(zhǎng)度遞增的順序產(chǎn)生最短路徑的方法。（具體見(jiàn)“七橋問(wèn)題”） 在加權(quán)連通圖中，尋求最短路徑的問(wèn)題有其實(shí)際背景，例如在某一國(guó)家或地區(qū)，城市與城市之間都互相連通，從一個(gè)城市到達(dá)另一城市存在著多條路徑，如何實(shí)現(xiàn)最短的路徑完成兩個(gè)城市之間的貨物運(yùn)輸就是一個(gè)解決圖論中實(shí)現(xiàn)最短路徑的問(wèn)題。 關(guān)鍵詞： 最短路徑 服務(wù)器 Dijkstra 算法 程序 Abstract in this paper, we firstly introduce the process of theory of graph. secondly, we give the introduction of the problem of shortest path and related content, and the application of works which a lot of severs have to search the shortest path. And then shows the one of shortest path algorithms: The Dijkstra algorithm. Finally, according to the ideas of this algorithm, we put forward a method to achieve the procedure using in the works. Key word Shortest— paths Sever Dijkstra Program 引 言 圖論 (Graph Theory)是數(shù)學(xué)的一個(gè)分支。若邊 e 標(biāo)記數(shù)為 k，則稱邊 e 的權(quán) (weight)為 k。如此進(jìn)行下去，直到圖中所有頂點(diǎn)都包括在第一 組中 ，或再也沒(méi)有可加入到第一組中的頂點(diǎn)存在為止。i++) { distance_shortest[i]=adjacent[source][i]。//保存最小值的號(hào) temp=distance_shortest[j]。 tmp = pre_node[tmp]。 cout 請(qǐng)輸入另一個(gè)端點(diǎn)號(hào)： 2endl。 ++i) distance_shortest[i] = infinity_value。在實(shí)際應(yīng)用中，需要求出任意兩點(diǎn)之間的最短路，