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

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

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

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

4、節(jié)點(diǎn))之間總權(quán)和最小的路徑就是最短路問題。最短路問題是網(wǎng)絡(luò)理論解決的典型問題之一，它不僅可以直接應(yīng)用于解決生產(chǎn)實(shí)際的許多問題，如管路鋪設(shè)、線路安裝、廠區(qū)布局和設(shè)備更新等，而且經(jīng)常被作為一個(gè)基本的工具，用于解決其他的做優(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)=