? ? ? ? 圖論是研究點(diǎn)、線間關(guān)系的一門學(xué)科?，F(xiàn)實(shí)生活中，凡是涉及到事物間的關(guān)系，都可以抽象為圖論模型。圖論模型也是各大數(shù)學(xué)建模中常見(jiàn)的一種模型，主要用于計(jì)算、規(guī)劃最短距離、路線等問(wèn)題。下面介紹幾個(gè)基本概念和算法。
?
單源最短路
? ? ? ? 單源最短路指的是構(gòu)造網(wǎng)絡(luò)中兩點(diǎn)間的最短路就是找到連接這兩個(gè)點(diǎn)的路徑中所有邊的權(quán)值之和為最小的通路。注意：在有向圖中，通路中所有的弧應(yīng)是首尾相連的。
? ? ? ? 單源最短路問(wèn)題就是求從一個(gè)點(diǎn)出發(fā)，到網(wǎng)絡(luò)其他各點(diǎn)的最短路求解單源最短路的常用算法是Dijkstra(迪杰斯特拉)算法，是由荷蘭人Edsger Wybe Dijkstra給出。
求解思路——從始點(diǎn)出發(fā)，逐步順序地向外探尋，每向外延伸一步都要求是最短的。
使用條件——網(wǎng)絡(luò)中所有的弧權(quán)均非負(fù)。
?
Dijkstra算法
? ? ? 本算法由Dijkstra在1959年提出，可用于求解指定兩點(diǎn)間的最短路，或從指定點(diǎn)到其余各點(diǎn)的最短路。目前被認(rèn)為是求無(wú)負(fù)權(quán)網(wǎng)絡(luò)最短路問(wèn)題的最好方法。算法思路基于以下原理：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-460121.html
? ? ? ? 若序列{vs,v1,..,vn-1,vn}是從vs 到vn的最短路，則序列{vs,v1,..,vn-1}是從vs 到vn-1 的最短路。此算法采用標(biāo)號(hào)法，可用兩種標(biāo)號(hào)：T 標(biāo)號(hào)(試探性)與P 標(biāo)號(hào)(永久性)。給vi 點(diǎn)一個(gè)P 標(biāo)號(hào)表示從vs 到vi 點(diǎn)的最短路權(quán)，vi 點(diǎn)的標(biāo)號(hào)不再改變。給vi 點(diǎn)一個(gè)T 標(biāo)號(hào)時(shí)，表示從vs 到vi 的估計(jì)最短路的上界，是一種臨時(shí)標(biāo)號(hào)，凡沒(méi)有得到P 標(biāo)號(hào)的都有T 標(biāo)號(hào)。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-460121.html
到了這里，關(guān)于【數(shù)學(xué)建模常用模型】圖論專題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
