本文關(guān)鍵詞：dijkstra算法，由筆耕文化傳播整理發(fā)布。

      或許在生活中，經(jīng)常會(huì)碰到針對(duì)某一個(gè)問(wèn)題，在眾多的限制條件下，如何去尋找一個(gè)最優(yōu)解？可能大家想到了很多諸如“線性規(guī)劃”，“動(dòng)態(tài)規(guī)劃”

這些經(jīng)典策略，當(dāng)然有的問(wèn)題我們可以用貪心來(lái)尋求整體最優(yōu)解，在圖論中一個(gè)典型的貪心法求最優(yōu)解的例子就莫過(guò)于“最短路徑”的問(wèn)題。

一：概序

   從下圖中我要尋找V0到V3的最短路徑，你會(huì)發(fā)現(xiàn)通往他們的兩點(diǎn)路徑有很多：V0->V4->V3，V0->V1->V3，當(dāng)然你會(huì)認(rèn)為前者是你要找的最短

路徑，那如果說(shuō)圖的頂點(diǎn)非常多，，你還會(huì)這么輕易的找到嗎？下面我們就要將剛才我們那點(diǎn)貪心的思維系統(tǒng)的整理下。

二：構(gòu)建

    如果大家已經(jīng)了解Prim算法，那么dijkstra算法只是在它的上面延伸了下，其實(shí)也是很簡(jiǎn)單的。

1.邊節(jié)點(diǎn)

  這里有點(diǎn)不一樣的地方就是我在邊上面定義一個(gè)vertexs來(lái)記錄貪心搜索到某一個(gè)節(jié)點(diǎn)時(shí)曾經(jīng)走過(guò)的節(jié)點(diǎn)，比如從V0貪心搜索到V3時(shí)，我們V3

的vertexs可能存放著V0,V4,V3這些曾今走過(guò)的節(jié)點(diǎn)，或許最后這三個(gè)節(jié)點(diǎn)就是我們要尋找的最短路徑。

1 #region 邊的信息 2 ///

  本文關(guān)鍵詞：dijkstra算法，由筆耕文化傳播整理發(fā)布。