最短路問(wèn)題的Gauss-Seidel矩陣算法.pdf

1、本文針對(duì)任意兩點(diǎn)間的最短路問(wèn)題，給出了一個(gè)改進(jìn)的矩陣算法——Gauss-Seidel矩陣算法，它同時(shí)具有檢測(cè)負(fù)回路的功能。證明了Gauss-Seidel矩陣算法的收斂速度不低于以往算法的收斂速度。特別是在求解大規(guī)模問(wèn)題時(shí)，該算法明顯優(yōu)于其它算法。此外，本文通過(guò)定義算符，給出了Gauss-Seidel矩陣算法的算符算法，使得Gauss-Seidel矩陣算法完全能夠并且可以很好地編程實(shí)現(xiàn)。仿真實(shí)驗(yàn)表明，Gauss-Seidel矩陣算法的確是

2、求解最短路問(wèn)題和檢測(cè)網(wǎng)絡(luò)中是否含有負(fù)回路的一種切實(shí)可行且高效的算法。 總體而言，本文首先介紹了最短路問(wèn)題、網(wǎng)絡(luò)優(yōu)化及其基礎(chǔ)知識(shí)，然后介紹了Gauss-Seidel矩陣算法和具有檢測(cè)負(fù)回路功能的Gauss-Seidel矩陣算法，并將其與最短路問(wèn)題的主要算法——矩陣算法和Floyd算法作了比較。算符的引入，圓滿地解決了以往算法在編程時(shí)遇到的∞問(wèn)題，并據(jù)此給出了Gauss-Seidel矩陣算法的算符算法。算符算法具有收斂速度快，存儲(chǔ)量