網(wǎng)絡(luò)最短路徑問題與應(yīng)用研究.pdf

1、最短路徑問題是網(wǎng)絡(luò)優(yōu)化問題的一個(gè)重要分支，主要求解的是網(wǎng)絡(luò)中任意兩個(gè)頂點(diǎn)之間的最優(yōu)路徑，其研究已經(jīng)有了相當(dāng)長(zhǎng)的歷史。最短路徑問題作為選擇最優(yōu)問題的基礎(chǔ)，在交通旅游、城市規(guī)劃以及工程技術(shù)等眾多應(yīng)用領(lǐng)域，已成為其分析與設(shè)計(jì)不可或缺的理論基礎(chǔ)。但目前針對(duì)求解小規(guī)模無回路網(wǎng)絡(luò)的最短路徑這一問題，大多數(shù)算法都是基于Dijkstra算法、Ford算法或者窮舉法的思想，不僅計(jì)算量龐大，而且操作復(fù)雜。針對(duì)這些問題，本文的主要工作如下：
　?。?）

2、根據(jù)本文介紹的幾種經(jīng)典算法本身的特性以及存在的缺陷性進(jìn)行深入分析，給出一種簡(jiǎn)單易行的“消弧”算法，旨在通過簡(jiǎn)化圖的結(jié)構(gòu)，不斷的消去網(wǎng)絡(luò)圖的中間節(jié)點(diǎn)和弧，進(jìn)而求得最短路徑及其長(zhǎng)度，并給出了算法的時(shí)間復(fù)雜度和可行性分析；
　　（2）根據(jù)“消弧”算法的思想提出的“矩陣”算法，不斷對(duì)網(wǎng)絡(luò)圖的權(quán)矩陣的第一行元素進(jìn)行分析處理，同時(shí)對(duì)其他行列的元素進(jìn)行消除，最終得到一個(gè)含有最短路徑長(zhǎng)度的稀疏矩陣，而求得最短路徑，之后給出了算法的時(shí)間復(fù)雜度和可行