網(wǎng)絡(luò)的K最短路分析及其在交通中的應(yīng)用.pdf

1、今天的社會(huì)已經(jīng)成為網(wǎng)絡(luò)社會(huì)，在今天的自然科學(xué)中，網(wǎng)絡(luò)研究也成為重要課題。交通網(wǎng)絡(luò)分析的重點(diǎn)是路徑分析，而路徑分析的核心為最優(yōu)路徑算法。最短路徑算法是最優(yōu)路徑算法中的一個(gè)經(jīng)典問題,它在實(shí)際生產(chǎn)生活中有廣泛應(yīng)用。在許多情況下，不僅僅要考慮最短路也要考慮次短路、次次短路，即K最短路問題。K最短路算法涉及很多領(lǐng)域，如在交通工程、通信、人工智能等方面有重要的實(shí)際意義。
　　本文在系統(tǒng)總結(jié)和分析經(jīng)典最短路算法、動(dòng)態(tài)規(guī)劃方法的基礎(chǔ)上，對(duì)聯(lián)網(wǎng)收費(fèi)

2、交通網(wǎng)絡(luò)中的多路徑問題進(jìn)行了深入細(xì)致的研究，得出了適用于交通網(wǎng)絡(luò)多路徑分析及模擬的高效、快速的K最短路算法。這一算法按長度遞增順序給出K最短路路徑排列。算法的復(fù)雜度為O m n n m k++(lg lg)。在給定的網(wǎng)絡(luò)中，通過添加標(biāo)識(shí)站對(duì)兩頂點(diǎn)之間K最短路徑識(shí)別，本文既給出標(biāo)識(shí)站的數(shù)目、位置的確定方法，又給出了整個(gè)網(wǎng)絡(luò)中添加標(biāo)識(shí)站的總方案數(shù)的計(jì)算方法。通過路徑伸展系數(shù)，采用啟發(fā)式搜索算法標(biāo)定高速公路網(wǎng)的路徑伸展系數(shù)的大小，從而確定高速