用matlab實現(xiàn)尋找最短路

1、1用matlab尋找賦權(quán)圖中的最短路中的應(yīng)用尋找賦權(quán)圖中的最短路中的應(yīng)用1引言引言圖論是應(yīng)用數(shù)學(xué)的一個分支，它的概念和結(jié)果來源都非常廣泛，最早起源于一些數(shù)學(xué)游戲的難題研究，如歐拉所解決的格尼斯堡七橋問題，以及在民間廣泛流傳的一些游戲的難題，如迷宮問題，博弈問題等。這些古老的難題，吸引了很多學(xué)者的注意。1847年，圖論應(yīng)用于分析電路網(wǎng)絡(luò)，這是它最早應(yīng)用于工程科學(xué)，以后隨著科學(xué)的發(fā)展，圖論在解決運籌學(xué)，網(wǎng)絡(luò)理論，信息論，控制論，博弈論以及計

2、算機科學(xué)等各個領(lǐng)域的問題時，發(fā)揮出很大的作用。在實踐中，圖論已成為解決自然科學(xué)，工程技術(shù)，社會科學(xué)，軍事等領(lǐng)域中許多問題的有力工具之一。最短路問題是圖論理論中的經(jīng)典問題，尋找最短路徑就是在指定網(wǎng)絡(luò)中兩節(jié)點間找一條距離最小的路。2最短路最短路2.12.1最短路的定義（shtpathproblem）對最短路問題的研究早在上個世紀60年代以前就卓有成效了，其中對賦權(quán)圖的有效算法是由荷蘭著名計算機專家E.W.Dijkstra在1959年首次提出

3、的該算法能??0ijw?夠解決兩指定點間的最短路也可以求解圖G中一特定點到其它各頂點的最短路。后來海斯在Dijkstra算法的基礎(chǔ)之上提出了海斯算法。但這兩種算法都不能解決含有負權(quán)的圖的最短路問題。因此由Fd提出了Fd算法它能有效地解決含有負權(quán)的最短路問題。但在現(xiàn)實生活中我們所遇到的問題大都不含負權(quán)所以我們在的情況下選擇Dijkstra算法。??0ijw?若網(wǎng)絡(luò)中的每條邊都有一個數(shù)值(長度、成本、時間等)，則找出兩節(jié)點(通常是源節(jié)點和阱

4、節(jié)點)之間總權(quán)和最小的路徑就是最短路問題。最短路問題是網(wǎng)絡(luò)理論解決的典型問題之一，它不僅可以直接應(yīng)用于解決生產(chǎn)實際的許多問題，如管路鋪設(shè)、線路安裝、廠區(qū)布局和設(shè)備更新等，而且經(jīng)常被作為一個基本的工具，用于解決其他的做優(yōu)化問題。3f(i=1:n)f(j=1:n)R(ij)=jendend%賦路徑初值f(k=1:n)f(i=1:n)f(j=1:n)if(D(ik)D(kj)D(ij))D(ij)=D(ik)D(kj)%更新dijR(ij)=