最短路徑問題圖論是數(shù)學(xué)的一個(gè)分支。它以圖為研究對(duì)象。圖論中的圖是由若干給定的點(diǎn)及連接兩點(diǎn)的線所構(gòu)成的圖形，這種圖形通常用來描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個(gè)事物間具有這種關(guān)系。圖論起源于著名的哥尼斯堡七橋問題。在哥尼斯堡的普萊格爾河上有七座橋?qū)⒑又械膷u及島與河岸聯(lián)結(jié)起來。問題是要從這四塊陸地中任何一塊開始，通過每一座橋正好一次，再回到起點(diǎn)。然而無數(shù)次的嘗試都沒有成功。歐拉在1736年解決了這個(gè)問題，他用抽像分析法將這個(gè)問題化為第一個(gè)圖論問題：即把每一塊陸地用一個(gè)點(diǎn)來代替，將每一座橋用聯(lián)接相應(yīng)的兩個(gè)點(diǎn)的一條線來代替，從而相當(dāng)于得到一個(gè)“圖”。歐拉證明了這個(gè)問題沒有解，并且推廣了這個(gè)問題，給出了對(duì)于一個(gè)給定的圖可以某種方式走遍的判定法則。這就是后來的歐拉路徑和歐拉回路。這項(xiàng)工作使歐拉成為圖論〔及拓?fù)鋵W(xué)〕的創(chuàng)始人。最短路徑問題是圖論解決的典型實(shí)際問題之一，可用來解決廠區(qū)布局、管路鋪設(shè)、線路安裝等實(shí)際問題。在日常生活中，我們?nèi)绻枰３Ｍ礎(chǔ)地區(qū)和B地區(qū)之間，我們最希望知道的可能是從A地區(qū)到B地區(qū)間的眾多路徑中，那一條路徑的路途最短。最短路徑問題是圖論研究中的一個(gè)經(jīng)典算法問題，旨在尋找圖（由結(jié)點(diǎn)和路徑組成的）中兩結(jié)點(diǎn)之間的最短路徑。算法具體的形式包括：（1）確定起點(diǎn)的最短路徑問題：即已知起始結(jié)點(diǎn)，求最短路徑的問題。（2）確定終點(diǎn)的最短路徑問題：與確定起點(diǎn)的問題相反，該問題是已知終結(jié)結(jié)點(diǎn)，求最短路徑的問題。在無向圖中該問題與確定起點(diǎn)的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)的確定起點(diǎn)的問題。（3）確定起點(diǎn)終點(diǎn)的最短路徑問題：即已知起點(diǎn)和終點(diǎn)，求兩結(jié)點(diǎn)之間的最短路徑。（4）全局最短路徑問題：求圖中所有的最短路徑。一、相關(guān)定義1.1圖一集元素及它們之間的某種關(guān)系稱為圖。具體地說，圖是一個(gè)二元組（V，E），其中集合V稱為頂點(diǎn)集，集合E是V中元素組成的某些無序?qū)Φ募?，稱為邊集。例：給定G=(V,E)，其中這便定義出一個(gè)圖。1.2賦權(quán)圖對(duì)圖G的每條邊e，賦以一個(gè)實(shí)數(shù)w(e)，稱為邊e的權(quán)。每個(gè)邊都賦有權(quán)的圖稱為賦權(quán)圖。權(quán)在不同的問題中會(huì)有不同的含義。例如交通網(wǎng)絡(luò)中，權(quán)可能表示運(yùn)費(fèi)、里程或道路的造價(jià)等。1.3最短路徑問題給定賦權(quán)圖G及G中兩點(diǎn)u,v，求u到v的具有最小權(quán)的路（稱為u到v的最短路）。注：賦權(quán)圖中路的權(quán)也稱為路的長(zhǎng)，最短(u，v)路的長(zhǎng)也稱為u，v間的距離，記為d(u，v)。最短路徑問題是圖論中的一個(gè)基本問題。在賦權(quán)圖中，每條邊都有一個(gè)數(shù)值——權(quán)（代表其長(zhǎng)度、成本、時(shí)間等），找出兩節(jié)點(diǎn)之間總權(quán)和最小的路徑就是最短路徑問題。最短路徑算法包括指定頂點(diǎn)對(duì)之間的最短路徑算法和所有頂點(diǎn)間的最短路徑算法，前者對(duì)于運(yùn)輸?shù)暮侠砘哂兄匾碚撘饬x，而后者的意義在于選擇合理的中轉(zhuǎn)中心，使得總的費(fèi)用最少。最短路問題是一個(gè)優(yōu)化問題，屬于網(wǎng)絡(luò)優(yōu)化和組合優(yōu)化的范疇。在圖論中最典型的兩種求最短路徑算法分別是Dijkstra算法和Floyd算法，其中Dijkstra算法適用于前者，而Floyd算法適用于后者。二、Dijkstra算法2.1

Dijkstra算法Dijkstra算法是典型最短路算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計(jì)算的節(jié)點(diǎn)很多，所以效率低。2.2

Dijkstra算法思想Dijkstra算法思想為：設(shè)G=(V,E)是一個(gè)帶權(quán)有向圖，把圖中頂點(diǎn)集合V分成兩組，第一組為已求出最短路徑的頂點(diǎn)集合（用S表示，初始時(shí)S中只有一個(gè)源點(diǎn)，以后每求得一條最短路徑,就將加入到集合S中，直到全部頂點(diǎn)都加入到S中，算法就結(jié)束了），第二組為其余未確定最短路徑的頂點(diǎn)集合（用U表示），按最短路徑長(zhǎng)度的遞增次序依次把第二組的頂點(diǎn)加入S中。在加入的過程中，總保持從源點(diǎn)v到S中各頂點(diǎn)的最短路徑長(zhǎng)度不大于從源點(diǎn)v到U中任何頂點(diǎn)的最短路徑長(zhǎng)度。此外，每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離，S中的頂點(diǎn)的距離就是從v到此頂點(diǎn)的最短路徑長(zhǎng)度，U中的頂點(diǎn)的距離，是從v到此頂點(diǎn)只包括S中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長(zhǎng)度。2.3

Dijkstra算法具體步驟以下面的例子說明如下圖，設(shè)A為源點(diǎn)，求A到其他各頂點(diǎn)（B、C、D、E、F）的最短路徑。線上所標(biāo)注為相鄰線段之間的距離，即權(quán)值。

算法執(zhí)行步驟如下表：步驟S集合中U集合中1選入A，此時(shí)S=<A>此時(shí)最短路徑A→A=0以A為中間點(diǎn)，從A開始找U=<B、C、D、E、F>A→B=6，A→C=3，A→其它U中的頂點(diǎn)=∞，發(fā)現(xiàn)A→C=3權(quán)值為最短2選入C，此時(shí)S=<A、C>此時(shí)最短路徑A→A=0，A→C=3以C為中間點(diǎn)，從A→C=3這條最短路徑開始找U=<B、D、E、F>A→C→B=5(比上面第一步的A→B=6要短)此時(shí)到D權(quán)值更改為A→C→B=5，A→C→D=6，A→C→E=7，A→C→其它U中的頂點(diǎn)=∞，發(fā)現(xiàn)A→C→B=5權(quán)值為最短3選入B，此時(shí)S=<A、C、B>此時(shí)最短路徑A→A=0，A→C=3，A→C→B=5以B為中間點(diǎn)從A→C→B=5這條最短路徑開始找U=<D、E、F>A→C→B→D=10(比上面第二步的A→C→D=6要長(zhǎng))此時(shí)到D權(quán)值更改為A→C→D=6，A→C→B→其它U中的頂點(diǎn)=∞，發(fā)現(xiàn)A→C→D=6權(quán)值為最短4選入D，此時(shí)S=<A、C、B、D>此時(shí)最短路徑A→A=0，A→C=3，A→C→B=5，A→C→D=6以D為中間點(diǎn)，從A→C→D=6這條最短路徑開始找U=<E、F>A→C→D→E=8(比上面第二步的A→C→E=7要長(zhǎng))此時(shí)到E權(quán)值更改為A→C→E=7，A→C→D→F=9發(fā)現(xiàn)A→C→E=7權(quán)值為最短5選入E，此時(shí)S=<A、C、B、D、E>此時(shí)最短路徑A→A=0，A→C=3，A→C→B=5，A→C→D=6，A→C→E=7，以E為中間點(diǎn)，從A→C→E=7這條最短路徑開始找U=<F>A→C→E→F=12(比上面第四步的A→C→D→F=9要長(zhǎng))此時(shí)到F權(quán)值更改為A→C→D→F=9發(fā)現(xiàn)A→C→D→F=9權(quán)值為最短6選入F，此時(shí)S=<A、C、B、D、E、F>此時(shí)最短路徑A→A=0，A→C=3，A→C→B=5，A→C→D=6，A→C→E=7，A→C→D→F=9U集合已空，查找完畢。三、Floyd算法3.1 Floyd算法的基本思想全部頂點(diǎn)間最短路徑算法具有代表性的是1962年由福勞德（Floyd）提出的算法。他的主要思想是從代表任意2個(gè)頂點(diǎn)vi到vj的距離的帶權(quán)鄰接矩陣開始，每次插入一個(gè)頂點(diǎn)vk，然后將vi到vj間的已知最短路徑與插入頂點(diǎn)vk作為中間頂點(diǎn)（一條路徑中除始點(diǎn)和終點(diǎn)外的其他頂點(diǎn)）時(shí)可能產(chǎn)生的vi到vj路徑距離比較，取較小值以得到新的距離矩陣，如此循環(huán)迭代下去，依次構(gòu)造出n個(gè)矩陣D(1)，D(2)，…，D(n)，當(dāng)所有的頂點(diǎn)均作為任意2個(gè)矩陣vi到vj中間頂點(diǎn)時(shí)得到的最后的帶權(quán)鄰接矩陣D(n)就反映了所有頂點(diǎn)對(duì)之間的最短距離信息，成為圖G的距離矩陣。最后對(duì)G中各行元素求和值并比較大小，決定單個(gè)或多個(gè)最佳的點(diǎn)。3.2Floyd算法構(gòu)造距離矩陣的原理對(duì)一個(gè)有n個(gè)頂點(diǎn)的圖G，將頂點(diǎn)用n個(gè)整數(shù)（從1到n）進(jìn)行編號(hào)。把G的帶權(quán)鄰接矩陣W作為距離的初值，即D(0)=(dij(0))nxm=W。第一步構(gòu)造D(1)=(dij(1))nxm，其中dij(1)=min{dij(0)，di1(0)+d1j(0)}是從vi到vj的只允許以v1作為中間點(diǎn)的路徑中最短路長(zhǎng)度。第二步構(gòu)造D(2)=(dij(2))nxm，其中dij(2)=min{dij(1)，di2(1)+d2j(1)}是從vi到vj的只允許以v1、v2作為中間點(diǎn)的路徑中最短路長(zhǎng)度。第n步構(gòu)造D(n)=(dij(n))nxm，其中dij(n)=min{dij(n)，din(n)+dnj(n)}是從vi到vj的只允許以v1、v2、…、vn作為中間點(diǎn)的路徑中最短路長(zhǎng)度，即是從vi到vj中間可插入任何頂點(diǎn)的路徑中最短路的長(zhǎng)度，因此D(n)即是距離矩陣。3.3Floyd算法具體步驟以下面的例子說明某城市考慮在開發(fā)區(qū)建立垃圾中轉(zhuǎn)站。在垃圾站的選址問題中，點(diǎn)表示可供選址的垃圾站，而其間的連線表示運(yùn)輸費(fèi)用，其需求點(diǎn)之間運(yùn)費(fèi)如圖所示（英文字母為可選垃圾站點(diǎn)，數(shù)字為相鄰站點(diǎn)之間的運(yùn)費(fèi)）。在垃圾中轉(zhuǎn)站的選址中，要求該中轉(zhuǎn)站到其他站點(diǎn)的距離最短，即運(yùn)輸費(fèi)用最少，這里通過運(yùn)用最短路徑Floyd算法可以求出該網(wǎng)點(diǎn)布局的最佳中轉(zhuǎn)站。abcde108433265首先，確定矩陣D(0)其中若頂點(diǎn)vi（編號(hào)i）到vj（編號(hào)j）有邊相連，則dij(0)abcde108433265然后，對(duì)k=1，2，3，…，n依次利用算法原理中第n步遞歸公式，由已知的Dn-1各元素確定Dn的各元素值。插入頂點(diǎn)a后D(1)的各元素和相應(yīng)的最短路徑因?yàn)閷?duì)稱性，D(1)的第一行元素和第一列元素與D(0)相同，D(1)的主對(duì)角線上的元素均為0，所以只需計(jì)算其余6個(gè)元素的值：由此可知，依次插入b，c，d，e，可得不斷更新的距離矩陣：最終求得距離矩陣D(5)的各元素值就是相應(yīng)頂點(diǎn)間的最短路徑。最后，計(jì)算第i行各元素值之和C(vi)即為vi到其他各點(diǎn)的