圖論中最有名的問(wèn)題可能就屬最短路徑了。最短路徑問(wèn)題要求解的是：如果從圖中某一頂點(diǎn)（稱為源點(diǎn)）到達(dá)另一頂點(diǎn)（稱為終點(diǎn)）的路徑可能不止一條昆淡，如何找到一條路徑，使得沿此路徑各邊上的權(quán)值總和（即從源點(diǎn)到終點(diǎn)的距離）達(dá)到最小刽严，這條路徑稱為最短路徑（shortestpath）昂灵。最短路徑有很多特殊的情況，包括有向圖還是無(wú)向圖舞萄，有沒(méi)有負(fù)權(quán)邊等眨补。這幾天我想介紹一下幾種常用的最短路徑算法。今天先講情況最簡(jiǎn)單（有向圖倒脓，沒(méi)有負(fù)權(quán)邊）撑螺，但也是最有名Dijkstra算法。
首先描述一下問(wèn)題：給定一個(gè)有向圖G和源點(diǎn)v崎弃，求v0到G中某個(gè)頂點(diǎn)u的最短路徑甘晤。限定各邊上的權(quán)值大于或等于0。
算法的基本思想很簡(jiǎn)單：所有的頂點(diǎn)饲做，按照它到源點(diǎn)v的距離线婚，客觀上存在一個(gè)從小到大的順序，我們只要按照這個(gè)順序找下去盆均，總有一步會(huì)找到目標(biāo)頂點(diǎn)u塞弊，而此時(shí)的距離就是u到源點(diǎn)v的距離。
想法簡(jiǎn)單泪姨，但關(guān)鍵是怎么按照“客觀存在的大小順序”計(jì)算各點(diǎn)到源點(diǎn)v的距離呢游沿？我們先簡(jiǎn)單思考一下，按照距離v的遠(yuǎn)近順序肮砾，v一定是排第一的诀黍，然后呢，排第二的一定是和v直接相連的點(diǎn)吧唇敞，否則總有一個(gè)點(diǎn)介于排第二的點(diǎn)和v之間蔗草，而它到v的距離肯定也比第二到v的距離近咒彤，那這個(gè)第二就有些名副其實(shí)了疆柔。比較麻煩的是，排第三的點(diǎn)在哪里镶柱？利用遞歸的想法就會(huì)發(fā)現(xiàn)旷档，排第三的點(diǎn)應(yīng)該從那些和v直接相連，或者和第二名直接相連的點(diǎn)中去尋找歇拆，否則第三名就會(huì)名副其實(shí)了鞋屈》蹲桑總結(jié)一下，需要找第n個(gè)點(diǎn)時(shí)厂庇，只需要在那些和前n-1個(gè)點(diǎn)直接相連的點(diǎn)里面找就行了渠啊。
Dijkstra算法的具體實(shí)現(xiàn)方法為：
1.設(shè)置兩個(gè)頂點(diǎn)的集合T和S：
a) S中存放已找到最短路徑的頂點(diǎn)，初始時(shí)权旷，集合S中只有一個(gè)頂點(diǎn)替蛉，即源點(diǎn)v0；
b) T中存放當(dāng)前還未找到最短路徑的頂點(diǎn)拄氯；
2.在T集合中選取當(dāng)前長(zhǎng)度最短的一條最短路徑(v0,…,vk)躲查，從而將vk加入到頂點(diǎn)集合S中，并修改源點(diǎn)v0到T中各頂點(diǎn)的最短路徑長(zhǎng)度译柏；重復(fù)這一步驟镣煮，直到所有的頂點(diǎn)都加入到集合S中，算法就結(jié)束了鄙麦。
下面給個(gè)用Dijkstra計(jì)算最短路徑的例子
1)首先求出長(zhǎng)度最短的一條最短路徑典唇，即頂點(diǎn)0到頂點(diǎn)2的最短路徑，其長(zhǎng)度為5黔衡，其實(shí)就是頂點(diǎn)0到其他各頂點(diǎn)的直接路徑中最短的路徑(v0→v2)蚓聘。
2)頂點(diǎn)2的最短路徑求出來(lái)以后，頂點(diǎn)0到其他各頂點(diǎn)的最短路徑長(zhǎng)度有可能要改變盟劫。例如從頂點(diǎn)0到頂點(diǎn)1的最短路徑長(zhǎng)度由∞縮短為20夜牡，從頂點(diǎn)0到頂點(diǎn)5的最短路徑長(zhǎng)度也由∞縮短為12。這樣長(zhǎng)度次短的最短路徑長(zhǎng)度就是在還未確定最終的最短路徑長(zhǎng)度的頂點(diǎn)中選擇最小的侣签，即頂點(diǎn)0到頂點(diǎn)5的最短路徑長(zhǎng)度塘装，為12，其路徑為(v0→v2→v5)影所。
3)頂點(diǎn)5的最短路徑求出來(lái)以后蹦肴，頂點(diǎn)0到其他各頂點(diǎn)的最短路徑長(zhǎng)度有可能要改變。例如從頂點(diǎn)0到頂點(diǎn)3的最短路徑長(zhǎng)度由30縮短為22猴娩，從頂點(diǎn)0到頂點(diǎn)4的最短路徑長(zhǎng)度也由∞縮短為30阴幌。這樣長(zhǎng)度第三短的最短路徑長(zhǎng)度就是在還未確定最終的最短路徑長(zhǎng)度的頂點(diǎn)中選擇最小的，即頂點(diǎn)0到頂點(diǎn)1的最短路徑長(zhǎng)度卷中，為20矛双，其路徑為(v0→v2→v1)。
4)此后再依次確定頂點(diǎn)0到頂點(diǎn)3的最短路徑(v0→v2→v5→v3)蟆豫，其長(zhǎng)度為22议忽；以及頂點(diǎn)0到頂點(diǎn)4的最短路徑(v0→v2→v1→v4)，其長(zhǎng)度為28十减。
