Matlab實(shí)現(xiàn)Flyod求最短距離及存儲(chǔ)最優(yōu)路徑

一、實(shí)際數(shù)據(jù)

　　已知圖中所有節(jié)點(diǎn)的X、Y坐標(biāo)。

? ?　　圖中的節(jié)點(diǎn)編號(hào)：矩陣中的編號(hào)

? ?　　　　J01-J62:1-62;

　　　　F01-F60:63-122;

　　　　Z01-Z06:123-128;

　　　　D01-D02:129-130.

?

二、Floyd求所有節(jié)點(diǎn)間的最小距離及通過(guò)矩陣存儲(chǔ)最優(yōu)路徑的節(jié)點(diǎn)

?

?

1 function [ optimal,path,maxnum ] = Floyd( distance,liantong,num,p,q ) 2 %Author:ljy 3 %Date:20170919 4 %弗洛伊德算法求最優(yōu)路徑和記錄下最優(yōu)路徑中的節(jié)點(diǎn)信息 5 %distance為節(jié)點(diǎn)間的連通距離。通過(guò)已知的節(jié)點(diǎn)的X、Y坐標(biāo)和連通矩陣計(jì)算而得。其中Inf為不連通節(jié)點(diǎn)間的距離。連通節(jié)點(diǎn)間的距離為正數(shù)（非Inf），連通情況通過(guò)連通（liantong）矩陣判斷所得。 6 %num為所有節(jié)點(diǎn)個(gè)數(shù) 7 %p和q為不考慮路徑的兩端節(jié)點(diǎn)編號(hào)。例如p=[129,129];q=[9,10];表示129到9、129到10的路不連通。 8 %optimal為最優(yōu)路徑的距離信息 9 %path為最優(yōu)路徑的路徑信息，行和列都為節(jié)點(diǎn)編號(hào)。path(i,j)為i到j(luò)的節(jié)點(diǎn)編號(hào)。例如：節(jié)點(diǎn)1到節(jié)點(diǎn)3的最優(yōu)路徑為1-》2-》3，那么path(1,3)=2;path(2,3)=3. 10 %maxnum：最長(zhǎng)的最優(yōu)路徑的節(jié)點(diǎn)總數(shù) 11 %liantong：節(jié)點(diǎn)間的連通情況，0為不連通，1為連通。 12 maxnum = 2; 13 14 15 %將distance變?yōu)猷徑泳仃?16 for i = 1:num 17 for j = 1:num 18 if distance(i,j) == 0 & i ~= j 19 distance(i,j) = Inf; 20 end 21 end 22 end 23 24 %將p與q之間的路徑的權(quán)重賦值為Inf，即不考慮p與q之間這條路徑的最優(yōu)路徑。p、q為0表示沒(méi)有不考慮的路徑 25 for i = 1:size(p) 26 for j = 1:size(q) 27 if p(i) > 0 & q(j) > 0 28 distance(p(i),q(j)) = Inf; 29 distance(q(j),p(i)) = Inf; 30 liantong(p(i),q(j)) = 0; 31 liantong(q(j),p(i)) = 0; 32 end 33 end 34 end 35 36 %核心算法 37 for k = 1:num 38 for i = 1:num 39 for j = 1:num 40 r = 2;%最優(yōu)路徑所包含的節(jié)點(diǎn)個(gè)數(shù) 41 if distance(i,j) > distance(i,k) + distance(k,j) 42 distance(i,j) = distance(i,k) + distance(k,j); 43 %存儲(chǔ)最優(yōu)路徑中的節(jié)點(diǎn) 44 p = i; 45 if liantong(p,j) ~= 0 46 while liantong(i,j) ~= liantong(p,k) & p ~= k 47 liantong(p,j) = liantong(p,k); 48 p = liantong(p,k); 49 r = r + 1; 50 end 51 else 52 liantong(p,j) = liantong(p,k); 53 r = r + 1; 54 end 55 end 56 if r > maxnum 57 maxnum = r; 58 end 59 end 60 end 61 end 62 63 %返回?cái)?shù)據(jù) 64 optimal = distance; 65 path = liantong; 66 end

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/landiljy/p/7567167.html

總結(jié)

以上是生活随笔為你收集整理的『实践』Matlab实现Flyod求最短距离及存储最优路径的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。