運(yùn)籌學(xué)中關(guān)于最短路問(wèn)題有兩種解決方法一種是逆序解法動(dòng)態(tài)規(guī)最短路徑算法,關(guān)鍵是將一個(gè)物理網(wǎng)絡(luò)結(jié)構(gòu)抽象為一個(gè)數(shù)學(xué)網(wǎng)絡(luò)結(jié)構(gòu),再利用數(shù)學(xué)方法進(jìn)行求解經(jīng)典Dijkstra算法的主要思想將頂點(diǎn)分成兩個(gè)集合S和T,已求出最短路的點(diǎn)置于S中,其它點(diǎn)置于T中。開(kāi)始時(shí)S中僅含起點(diǎn)vs,其它點(diǎn)全在T中,隨著求最短路迭代工作的進(jìn)行,S中的點(diǎn)逐漸增多,當(dāng)終點(diǎn)vt也被納入S中時(shí),迭代結(jié)束。為了便于計(jì)算和區(qū)分各頂點(diǎn)是否已進(jìn)入集合S,給已求出到起點(diǎn)最短路的點(diǎn)vk賦以標(biāo)號(hào)。這個(gè)標(biāo)號(hào)由兩部分組成,記為(d(vs,vk),i)其中i為vk...