迪克斯屈拉最短路徑算法圖論論(已修改)
2025-01-19 03:16 本頁(yè)面
【正文】 姓名： 沈敬紅 學(xué)院：通信學(xué)院 學(xué)號(hào)： s140131109 1 計(jì)算機(jī)網(wǎng)絡(luò)中迪克斯屈拉 最短路徑 算法 的程序?qū)崿F(xiàn)及應(yīng)用 沈敬紅 S140131109 重慶郵電大學(xué)通信與信息工程學(xué)院 摘要： 本文首先介紹了圖論的發(fā)展歷程，介紹了圖論在實(shí)際問(wèn)題中的應(yīng)用。其次，介紹了圖論中最短路徑的問(wèn)題及相關(guān)內(nèi)容，介紹了計(jì)算機(jī)網(wǎng)絡(luò)中服務(wù)器之間存在的最短路徑問(wèn)題。然后，介紹了迪克斯屈拉（ Dijkstra）最短路徑算法。最后，依據(jù)算法的思想，分別實(shí)現(xiàn)了 Dijkstra 算法在求解計(jì)算網(wǎng)絡(luò)最短路徑的應(yīng)用程序。 關(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è)分支。它以圖為研究對(duì)象。圖論中的圖是由若干給定的點(diǎn)及連接兩點(diǎn)的線所構(gòu)成的圖形，這種圖形通常用來(lái)描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個(gè)事物間具有這種關(guān)系。 圖論本身是應(yīng)用數(shù)學(xué)的一部份，因此，歷史上圖論曾經(jīng)被好多位數(shù)學(xué)家各自獨(dú)立地建立過(guò)。關(guān)于圖論的文字記載最早出現(xiàn)在歐拉 1736 年的論著中，他所考慮的原始問(wèn)題有很強(qiáng)的實(shí)際背景。 圖論的發(fā)展已有 200 多年的歷史，它發(fā)源于 18 世紀(jì)普魯士的柯尼斯堡。當(dāng)?shù)氐木用裣胫滥芊駨娜我庖魂懙爻霭l(fā)，走遍聯(lián)接該城的 7 座橋又回到原地 ? 其條 件是每座橋都經(jīng)過(guò)一次并且只經(jīng)過(guò)一次。（具體見“七橋問(wèn)題”） 在加權(quán)連通圖中，尋求最短路徑的問(wèn)題有其實(shí)際背景，例如在某一國(guó)家或地區(qū)，城市與城市之間都互相連通，從一個(gè)城市到達(dá)另一城市存在著多條路徑，如何實(shí)現(xiàn)最短的路徑完成兩個(gè)城市之間的貨物運(yùn)輸就是一個(gè)解決圖論中實(shí)現(xiàn)最短路徑的問(wèn)題。同樣，比如需要架設(shè)電網(wǎng)、通信網(wǎng)絡(luò)以及其他的有線網(wǎng)絡(luò)，基于全網(wǎng)的考慮之下，點(diǎn)和點(diǎn)之間怎樣架設(shè)一條最短的線路就是一個(gè)實(shí)際的最短路問(wèn)題。按照?qǐng)D論的表述，在一個(gè)圖中，兩點(diǎn)之間的路徑可能有很多條，且每條路徑所經(jīng)過(guò)的邊數(shù)可能是不同的，如果是網(wǎng)絡(luò)，每 條路徑的各邊權(quán)數(shù)之和也可能是不同的，怎樣找到一條頂點(diǎn)對(duì)頂點(diǎn)之間的各邊權(quán)數(shù)之和為最小的路徑問(wèn)題稱為最短路問(wèn)題 [1]。 本文提出了一個(gè)計(jì)算機(jī)網(wǎng)絡(luò)中服務(wù)器之間最短路徑的問(wèn)題背景，并在迪克斯屈拉（ Dijkstra） 算法的基礎(chǔ)上，實(shí)現(xiàn)算法在服務(wù)器之間尋求最短路徑的程序設(shè)計(jì)。 姓名： 沈敬紅 學(xué)院：通信學(xué)院 學(xué)號(hào)： s140131109 2 圖論相關(guān)概念 [1,2]： 無(wú)向圖：每一條邊都是無(wú)向邊的圖稱為無(wú)向圖。 鏈：設(shè) u 和 v 是任意圖 G 的頂點(diǎn)，圖 G 的一條 uv 鏈（ chain 或 walk）是有限
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1