數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)最短路問題實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)內(nèi)容1、了解最短路的算法及其應(yīng)用

2、會(huì)用Matlab軟件求最短路1、圖論的基本概念2、最短路問題及其算法3、最短路的應(yīng)用4、建模案例：最優(yōu)截?cái)嗲懈顔栴}5、實(shí)驗(yàn)作業(yè)圖論的基本概念一、圖的概念1、圖的定義2、頂點(diǎn)的次數(shù)3、子圖二、圖的矩陣表示1、關(guān)聯(lián)矩陣2、鄰接矩陣返回定義

有序三元組G=(V,E,

Y)稱為一個(gè)圖.

V={v1

,v2

,,vn

}是有窮非空集，稱為頂點(diǎn)集，其中的元素叫圖G

的頂點(diǎn).E

稱為邊集，其中的元素叫圖G

的邊.Y

是從邊集E

到頂點(diǎn)集V

中的有序或無(wú)序的元素 偶對(duì)的集合的映射，稱為關(guān)聯(lián)函數(shù).例1設(shè)G=(V,E,Y

)，其中V={v1

,v2

,v3

,v4}，E={e1,

e2

,

e3,

e4,

e5},Y

(e1

)

=

v1v2

,

Y

(e2

)

=

v1v3

,

Y

(e3

)

=

v1v4

,

Y

(e4

)

=

v1v4

,

Y

(e5

)

=

v3v3

.G

的圖解如圖.圖的定義定義

在圖

G

中，與

V

中的有序偶(vi，

vj)對(duì)應(yīng)的邊

e，稱為圖的有向邊（或弧），而與V

中頂點(diǎn)的無(wú)序偶vivj

相對(duì)應(yīng)的邊e，稱為圖的無(wú)向邊.每一條邊都是無(wú)向邊的圖，叫無(wú)向圖；每一條邊都是有向邊的圖，稱為有向圖；既有無(wú)向邊又有有向邊的圖稱為混合圖.定義若將圖G

的每一條邊e

都對(duì)應(yīng)一個(gè)實(shí)數(shù)w(e)，稱w(e)為邊的權(quán)，并稱圖G

為賦權(quán)圖.規(guī)定用記號(hào)n

和e

分別表示圖的頂點(diǎn)數(shù)和邊數(shù).常用術(shù)語(yǔ)：（１）端點(diǎn)相同的邊稱為環(huán)．（２）若一對(duì)頂點(diǎn)之間有兩條以上的邊聯(lián)結(jié)，則這些邊稱為重邊．（３）有邊聯(lián)結(jié)的兩個(gè)頂點(diǎn)稱為相鄰的頂點(diǎn)，有一個(gè)公共端點(diǎn)的邊稱為相鄰的邊．（４）邊和它的端點(diǎn)稱為互相關(guān)聯(lián)的．（５）既沒有環(huán)也沒有平行邊的圖，稱為簡(jiǎn)單圖．（６）任意兩頂點(diǎn)都相鄰的簡(jiǎn)單圖，稱為完備圖，記為Kn，其中n為頂點(diǎn)的數(shù)目．(7)若V=X

¨

Y，X

˙

Y=F

，X

中任兩頂點(diǎn)不相鄰，Y

中任兩頂點(diǎn)不相鄰，稱G

為二元圖；若X

中每一頂點(diǎn)皆與Y

中一切頂點(diǎn)相鄰，稱為完備二元圖，記為Km,n，其中m,n

分別為X

與Y

的頂點(diǎn)數(shù)目．返回頂點(diǎn)的次數(shù)定義

（１）在無(wú)向圖中，與頂點(diǎn)v

關(guān)聯(lián)的邊的數(shù)目（環(huán)算兩次）稱為

v

的次數(shù)，記為

d(v)．（２）在有向圖中，從頂點(diǎn)v

引出的邊的數(shù)目稱為v

的出度，記為d+(v)，從頂點(diǎn)v

引入的邊的數(shù)目稱為的入度，記為d-(v)，d(v)=d+(v)+d-(v)稱為v

的次數(shù)．d

(

v

4

)

=

444d

(

v

4

)

=

5d

+

(

v

)

=

2d

-

(

v

)

=

3定理１

d

(v)

=

2e(G)v?V

(G

)推論１

任何圖中奇次頂點(diǎn)的總數(shù)必為偶數(shù)．例在一次聚會(huì)中，認(rèn)識(shí)奇數(shù)個(gè)人的人數(shù)一定是偶數(shù)。返回子圖定義

設(shè)圖

G=(V,E,

Y

),G1=(V1,E1,

Y

1

)若

V1

?

V，E1

?

E,且當(dāng)

e

?

E1

時(shí)，

Y

1

(e)=

Y

(e),則稱

G1是G的子圖．特別的，若

V1=V，則

G1

稱為G

的生成子圖．設(shè)V1?

V，且V1

?F

，以V1

為頂點(diǎn)集、兩個(gè)端點(diǎn)都在V1

中的圖G

的邊為邊集的圖G

的子圖，稱為G

的由V1

導(dǎo)出的子圖，記為G[V1].設(shè)E1?

E,且E1

?F

,以E1

為邊集,E1

的端點(diǎn)集為頂點(diǎn)集的圖G

的子圖,稱為G

的由E1

導(dǎo)出的子圖,記為G[E1].GG[{v1,v4,v5}]G[{e1,e2,e3}]返回關(guān)聯(lián)矩陣對(duì)無(wú)向圖Ｇ，其關(guān)聯(lián)矩陣Ｍ＝

(mij

)n·e

，其中：ij若vi

與ej

相關(guān)聯(lián)若vi

與ej

不關(guān)聯(lián)m0=

131

v4

0M=

1對(duì)有向圖Ｇ，其關(guān)聯(lián)矩陣Ｍ＝

(mij

)n·e

，其中：ij若vi

是ej的起點(diǎn)若vi

是ej的終點(diǎn)若vi

與ej

不關(guān)聯(lián)m

=

-1

0

1注：假設(shè)圖為簡(jiǎn)單圖e1

e2

e3

e4

e5

1

0

0

0 1

v11

0

1

0

v2

0

1

1

0

v

0

1

1

0返回鄰接矩陣對(duì)無(wú)向圖Ｇ，其鄰接矩陣A

=(aij

)n·n

，其中：ij若vi

與v

j

相鄰若vi

與v

j

不相鄰a0=

13

v注：假設(shè)圖為簡(jiǎn)單圖v1

v2

v3

v40

1

0

1

v11

0

1

1

v20

1

0

11

1

1

0

v4A=

aij若（vi，v

j）ˇ

E對(duì)有向圖Ｇ＝（Ｖ，Ｅ），其鄰接矩陣A

=(aij

)n·n

，其中：若（vi，v

j）?

E0=

1對(duì)有向賦權(quán)圖Ｇ，其鄰接矩陣A

=(aij

)n·n

，其中：

￥

wijij

a

=

0若(vi,v

j

)?

E,且wij

為其權(quán)若i

=j若(vi

,v

j

)ˇ

E無(wú)向賦權(quán)圖的鄰接矩陣可類似定義．3A=

v1

v2

v3

v40

2

￥

7

v12

0

8

3

v2￥

8

0

5

v7

3

5

0

v4返回最短路問題及其算法一、基本概念二、固定起點(diǎn)的最短路三、每對(duì)頂點(diǎn)之間的最短路返回基本概念1

4通路Wv

v1

4道路Tv

v1

4路徑Pv

v=

v1e4

v4

e5

v2

e1v1e4

v4=

v1e1v2

e5

v4

e6

v2

e2

v3e3v4=

v1e1v2

e5

v4定義１

在無(wú)向圖

G=(V,E,

Y

)中：（１）頂點(diǎn)與邊相互交錯(cuò)且

Y

(ei

)

=

vi-1vi

(i=1,2,…k)的有限非空序列w

=(v0

e1v1e2

vk

-1ek

vk

)稱為一條從v0

到vk

的通路，記為Wv

v0

k（２）邊不重復(fù)但頂點(diǎn)可重復(fù)的通路稱為道路，記為Tv

v0

k（３）邊與頂點(diǎn)均不重復(fù)的通路稱為路徑，記為Pv

v0

k定義２

（１）任意兩點(diǎn)均有路徑的圖稱為連通圖．（２）起點(diǎn)與終點(diǎn)重合的路徑稱為圈．（３）連通而無(wú)圈的圖稱為樹．定義３

（１）設(shè)

P(u,v)是賦權(quán)圖

G

中從

u

到

v

的路徑，則稱w(P)

=

w(e)

為路徑

P

的權(quán)．e?

E

(

P

)(2)

在賦權(quán)圖G

中，從頂點(diǎn)u

到頂點(diǎn)v

的具有最小權(quán)的路P*

(u,v)，稱為u

到v

的最短路．返回固定起點(diǎn)的最短路最短路是一條路徑，且最短路的任一段也是最短路．假設(shè)在u0-v0的最短路中只取一條，則從u0到其余頂點(diǎn)的最短路將構(gòu)成一棵以u(píng)0為根的樹．因此,

可采用樹生長(zhǎng)的過程來(lái)求指定頂點(diǎn)到其余頂點(diǎn)的最短路．Dijkstra

算法：求G

中從頂點(diǎn)u0

到其余頂點(diǎn)的最短路設(shè)G

為賦權(quán)有向圖或無(wú)向圖，G

邊上的權(quán)均非負(fù)．對(duì)每個(gè)頂點(diǎn)，定義兩個(gè)標(biāo)記（

l(v)，z(v)），其中:l(v)：表從頂點(diǎn)u0

到v

的一條路的權(quán)．z(v)：v

的父親點(diǎn)，用以確定最短路的路線算法的過程就是在每一步改進(jìn)這兩個(gè)標(biāo)記，使最終l(v)為從頂點(diǎn)u0

到v

的最短路的權(quán)．S：具有永久標(biāo)號(hào)的頂點(diǎn)集輸入:G

的帶權(quán)鄰接矩陣w(u,v)算法步驟：中的頂點(diǎn)，則令S=S∪（3）

設(shè)v

*

是使l

(v

)取最小值的S{

v

*

}，u

?v

*（4）

若

S

?

φ，轉(zhuǎn)

2，否則，停止.用上述算法求出的l(v)就是u0

到v

的最短路的權(quán)，從v

的父親標(biāo)記

z(v)

追溯到u0

,

就得到u0

到v

的最短路的路線.（１）賦初值：令

S＝{

u0

},

l(u0

)

=0"

v

?

S

=

V

\

S

,令l(v)

=

W

(u0

,

v)

,

z(v)

=

u0u

?

u0（2）更新

l(v)

、

z(v)

：

"

v

?

S

=

V

\

S

,若

l(v)

>

l(u)

+

W

(u,

v)則令l(v)

=

l(u)

+

W

(u,

v)

,

z(v)

=

u例

求下圖從頂點(diǎn)u1

到其余頂點(diǎn)的最短路．￥0

6

3

0

409051203￥218￥￥￥￥

0￥61￥￥￥

07￥￥9￥

0先寫出帶權(quán)鄰接矩陣：

W

=因G

是無(wú)向圖，故W

是對(duì)稱陣．l(ui

)迭代次數(shù)1u2u34u

u5u67u

u8u１6０￥￥￥￥￥￥￥z(v)20２１８￥￥￥￥328￥￥10￥483￥10￥5861012771012891212最后標(biāo)記:l(v)021736912u1

u1

u1u6u2u5

u4

u5l

(ui

)u1u2u3u4u5u6u7u8最后標(biāo)記:l(v)z(v)021736912u1u1u1u6u2u5u

4u5u1u2u3u4u5u6u7u8返回每對(duì)頂點(diǎn)之間的最短路（一）算法的基本思想(二)算法原理1、求距離矩陣的方法2、求路徑矩陣的方法3、查找最短路路徑的方法（三）算法步驟返回算法的基本思想依次構(gòu)造出n

個(gè)矩陣D(1)、直接在圖的帶權(quán)鄰接矩陣中用插入頂點(diǎn)的方法D(2)、…、D(n

)，使最后得到的矩陣D(n

)成為圖的距離矩陣，同時(shí)也求出插入點(diǎn)矩陣以便得到兩點(diǎn)間的最短路徑．返回算法原理——

求距離矩陣的方法ij

n·n把帶權(quán)鄰接矩陣W

作為距離矩陣的初值，即D(0)=(d

(0))=Wij

n·nij（１）D(1)=

(d

(1))

，其中d

(1)=

min{d

(0)

,

d

(0)

+

d

(0)

}ij

i1 1

jijd

(1)是從vi

到vj

的只允許以v1

作為中間點(diǎn)的路徑中最短路的長(zhǎng)度．ij

n·nij（2）D(2)=

(d

(2))

，其中d

(2)=

min{d

(1)

,

d

(1)

+

d

(1)

}ij i

2 2

jd

(2)是從vi

到vj

的只允許以v1

、v2

作為中間點(diǎn)的路徑中最短路的長(zhǎng)度．ij…(

)(n

)ij

n·n（n

）D

n

=

(dij

ij)

，其中d

(n

)in

nj=

min{d

(n

-1)

,

d

(n

-1)

+

d

(n

-1)

}(n

)ijd、

、n是從

vi

到

vj

的只允許以

v1

v2

…、v

作為中間點(diǎn)的路徑中最短路的長(zhǎng)度．即是從vi

到vj

中間可插入任何頂點(diǎn)的路徑中最短路的長(zhǎng)，因此D(n

)即是距離矩陣．返回算法原理——

求路徑矩陣的方法ij

n·n,ij=

(r

(0)

)

=

jR

(0)

r

(0)每求得一個(gè)D(k)時(shí)，按下列方式產(chǎn)生相應(yīng)的新的R(k)ik

kj否則ij

ij(k

)若d

(k

-1)

>

d

(k

-1)

+

d

(k

-1)=

r

(k

-1)krij在建立距離矩陣的同時(shí)可建立路徑矩陣R．R=(rij

)n·n

,rij

的含義是從vi

到vj

的最短路要經(jīng)過點(diǎn)號(hào)為rij

的點(diǎn)．即當(dāng)vk被插入任何兩點(diǎn)間的最短路徑時(shí)，被記錄在R(k)中，依次求

Dν求得Rν

，可由Dν

來(lái)查找任何點(diǎn)對(duì)之間最短路的路徑．返回ij算法原理——

查找最短路路徑的方法ij

1若r

(n

)=p

，則點(diǎn)p1

是點(diǎn)i

到點(diǎn)j

的最短路的中間點(diǎn).然后用同樣的方法再分頭查找．若：k（１）向點(diǎn)

i

追朔得：

r

(n

)

=

p

,

r

(n

)

=

p

,…,

r

(n

)

=

pip1

2

ip2

3

ipk（２）向點(diǎn)

j

追朔得：

r

(n

)

=

q

,

r

(n

)

=

q

,…,

r

(n

)

=

jp1

j

1

q1

j

2

qm

jpkp3

p2

p1q1q2qm則由點(diǎn)i到j(luò)的最短路的路徑為：i,

pk

,,

p2

,

p1,

q1

,

q2

,,

qm

,

j返回算法步驟Floyd

算法：求任意兩點(diǎn)間的最短路．D(i,j)：i

到

j

的距離．R(i,j)：i到

j之間的插入點(diǎn)．輸入:

帶權(quán)鄰接矩陣

w(i,j)（１）賦初值：對(duì)所有

i,j,d(i,j)

?

w(i,j),r(i,j)

?

j,

k

?

1(2)

更新d(i,j),r(i,j)對(duì)所有i,j，若d(i,k)+d(k,j)<d(i,j)，則d(i,j)?d(i,k)+d(k,j),

r(i,j)

?k(3)

若

k=n

，停止．否則

k

?

k+1，轉(zhuǎn)（２）．例求下圖中加權(quán)圖的任意兩點(diǎn)間的距離與路徑．

5

33

43

15

4

1

4

4

4 4

3

2

3

3 3

2

3

43

3

430

96

3

5

0

7

5

3

9

7

0

2

4 6

2

0

24

2

06

4

64

,

R

=D

=d51

=9

，故從v5

到v1

的最短路為９．r51

＝４．由

v4

向

v5

追朔：

r54

=

3,

r53

=

3

;由v4

向v1

追朔：r41

=1所以從v5

到v1

的最短路徑為：5

fi

3

fi4

fi

1.返回最短路的應(yīng)用一、可化為最短路問題的多階段決策問題二、選址問題1、中心問題2、重心問題返回可化為最短路問題的多階段決策問題例1設(shè)備更新問題：企業(yè)使用一臺(tái)設(shè)備，每年年初，企業(yè)領(lǐng)導(dǎo)就第一年第二年第三年第四年第五年1111121213要確定是購(gòu)置新的，還是繼續(xù)使用舊的.若購(gòu)置新設(shè)備，就要支付一定的購(gòu)置費(fèi)用；若繼續(xù)使用，則需支付一定的維修費(fèi)用.現(xiàn)要制定一個(gè)五年之內(nèi)的設(shè)備更新計(jì)劃，使得五年內(nèi)總的支付費(fèi)用最少.已知該種設(shè)備在每年年初的價(jià)格為：使用不同時(shí)間設(shè)備所需維修費(fèi)為：使用年限0－11－22－33－44－5維修費(fèi)5681118構(gòu)造加權(quán)有向圖G1(V,E)ib

ir（1）頂點(diǎn)集

V＝{

X

,

i=1,2,3,4,5}∪{

X

(

k

)

,i=2,3,4,5,6;

k=1,2,…,i-1},每個(gè)頂點(diǎn)代表年初的一種決策，其中頂點(diǎn)

X

ib

代表第

i

年初購(gòu)置新設(shè)備ir的決策，頂點(diǎn)X

(k

)代表第i

年初修理用過k

年的舊設(shè)備的決策（

2）弧集E={

(

X

,

Xib

i

+1,b),

(

X

(

k

)

,

Xir

i

+1,b),

i=

1,2,3,4;

k=

1,2,…

,i-1}∪

{

(

X,

X

(1)ib

i

+1,r

ir

i

+1,r)

,

i=

1,2,3,4,5}∪

{

(

X

(

k

)

,

X

(

k

+1)

)

,i=

1,2,3,4,5;k=

1,2,i-1}若第i

年初作了決策X

i

后，第i+1

年初可以作決策X

i

+1

，則頂點(diǎn)X

i

與X

i

+1

之間有弧(X

i

,X

i

+1

)，其權(quán)W(X

i

,X

i

+1

)代表第i

年初到第i+1

年3b

4

r初之間的費(fèi)用.例如，弧

(

X

,

X

(1)

)

代表第3

年初買新設(shè)備，第四年初決定用第三年買的用過一年的舊設(shè)備，其權(quán)則為第三年初的購(gòu)置費(fèi)與三、四年間的維修費(fèi)之和，為12＋5

＝

171b

6r（3）問題轉(zhuǎn)化為頂點(diǎn)

X

到

X

(

k

)

的最短路問題.五年的最優(yōu)購(gòu)置費(fèi)為1b

6rk

=1,2,3,4,5min{d

(

X

,

X

(

k

)

)}其中

d(

X

,

X

(

k

)

)為頂點(diǎn)

X

到

X

(

k

)

的最短路的權(quán).1b

6r

1b

6r求得最短路的權(quán)為53

，而兩條最短路分別為

1b6

rX

-

X-

X-

X

-

X-

X(

1)2

r(

2

)3

r

4

b(

1)5

r(

2

)

;1bX

-

X-

X

-

X-

X-

X(

1)2

r

3b(

1)4

r(

2

)5

r(

3

)6

r因此，計(jì)劃為第一、三年初購(gòu)置新設(shè)備，或第一、四年初購(gòu)置新設(shè)備，

五年費(fèi)用均最省，為53.也可構(gòu)造加權(quán)有向圖G2(V,E).（1）頂點(diǎn)集V={V1

,V2

,V3

,V4

,V5

,V6

}，Vi

表第

i

年初購(gòu)置新設(shè)備的決策，

V6表第五年底.（2）弧集E={(Vi

,V

j

)，i=1,2,3,4,5;i<j≤6},弧(Vi

,V

j

)表第i

年初購(gòu)進(jìn)一臺(tái)設(shè)備一直使用到第j年初的決策，其權(quán)W

(Vi

,V

j

)表由這一決策在第i

年初到第j

年初的總費(fèi)用，如W

(V1

,V4

)

=11+5+6+8=30.（3）問題轉(zhuǎn)化為求V1到V6

的最短路問題，求得兩條最短路為V1

–V4

–V6

，V1

–V3

–V6，權(quán)為53，與圖G1(V,E)的解相同．返回1￡

j

￡nS

(vi

)

=

max{dij}i

=

1,2,n選址問題--中心問題例

2

某城市要建立一個(gè)消防站，為該市所屬的七個(gè)區(qū)服務(wù)，如圖所示．問應(yīng)設(shè)在那個(gè)區(qū)，才能使它至最遠(yuǎn)區(qū)的路徑最短．用Floyd

算法求出距離矩陣D=(d