❶ Floyd演算法除了能求出最短距離值外,還能求出最短路徑嗎它和Dijstra演算法有什麼區別
Floyd演算法可以求出最短路徑 但要求除了距離矩陣之外 還要保存一個結果矩陣 用結果矩陣還原出最短路
Floyd演算法跟Dijstra演算法最主要的區別在於 Floyd演算法可以給出所有頂點間的最短路徑 而Dijstra只能給出從一個特定頂點到其他頂點的最短路徑 同時 Floyd演算法的復雜度為O(V^3) 而Dijstra的復雜度是 O(E+VlogV) (用斐波那契堆)
❷ 最短路徑 | 深入淺出Dijkstra演算法（一）
上次我們介紹了神奇的只有 五行的 Floyd-Warshall 最短路演算法 ，它可以方便的求得 任意兩點的最短路徑， 這稱為 「多源最短路」。
這次來介紹 指定一個點（源點）到其餘各個頂點的最短路徑， 也叫做 「單源最短路徑」。 例如求下圖中的 1 號頂點到 2、3、4、5、6 號頂點的最短路徑。
與 Floyd-Warshall 演算法一樣，這里仍然 使用二維數組 e 來存儲頂點之間邊的關系， 初始值如下。
我們還需要用 一個一維數組 dis 來存儲 1 號頂點到其餘各個頂點的初始路程， 我們可以稱 dis 數組為 「距離表」， 如下。
我們將此時 dis 數組中的值稱為 最短路的「估計值」。
既然是 求 1 號頂點到其餘各個頂點的最短路程， 那就 先找一個離 1 號頂點最近的頂點。
通過數組 dis 可知當前離 1 號頂點最近是 2 號頂點。 當選擇了 2 號頂點後，dis[2]的值就已經從「估計值」變為了「確定值」， 即 1 號頂點到 2 號頂點的最短路程就是當前 dis[2]值。
為什麼呢？你想啊， 目前離 1 號頂點最近的是 2 號頂點，並且這個圖所有的邊都是正數，那麼肯定不可能通過第三個頂點中轉，使得 1 號頂點到 2 號頂點的路程進一步縮短了。 因此 1 號頂點到其它頂點的路程肯定沒有 1 號到 2 號頂點短，對吧 O(∩_∩)O~
既然選了 2 號頂點，接下來再來看 2 號頂點 有哪些 出邊 呢。有 2->3 和 2->4 這兩條邊。
先討論 通過 2->3 這條邊能否讓 1 號頂點到 3 號頂點的路程變短。 也就是說現在來比較 dis[3] 和 dis[2]+e[2][3] 的大小。其中 dis[3]表示 1 號頂點到 3 號頂點的路程，dis[2]+e[2][3]中 dis[2]表示 1 號頂點到 2 號頂點的路程，e[2][3]表示 2->3 這條邊。所以 dis[2]+e[2][3]就表示從 1 號頂點先到 2 號頂點，再通過 2->3 這條邊，到達 3 號頂點的路程。
我們發現 dis[3]=12，dis[2]+e[2][3]=1+9=10，dis[3]>dis[2]+e[2][3]，因此 dis[3]要更新為 10。這個過程有個專業術語叫做 「鬆弛」 。即 1 號頂點到 3 號頂點的路程即 dis[3]，通過 2->3 這條邊 鬆弛成功。 這便是 Dijkstra 演算法的主要思想： 通過 「邊」 來鬆弛 1 號頂點到其餘各個頂點的路程。
同理通過 2->4（e[2][4]），可以將 dis[4]的值從 ∞ 鬆弛為 4（dis[4]初始為 ∞，dis[2]+e[2][4]=1+3=4，dis[4]>dis[2]+e[2][4]，因此 dis[4]要更新為 4）。
剛才我們對 2 號頂點所有的出邊進行了鬆弛。鬆弛完畢之後 dis 數組為：
接下來，繼續在剩下的 3、4、5 和 6 號頂點中，選出離 1 號頂點最近的頂點。通過上面更新過 dis 數組，當前離 1 號頂點最近是 4 號頂點。此時，dis[4]的值已經從「估計值」變為了「確定值」。下面繼續對 4 號頂點的所有出邊（4->3，4->5 和 4->6）用剛才的方法進行鬆弛。鬆弛完畢之後 dis 數組為：
繼續在剩下的 3、5 和 6 號頂點中，選出離 1 號頂點最近的頂點，這次選擇 3 號頂點。此時，dis[3]的值已經從「估計值」變為了「確定值」。對 3 號頂點的所有出邊（3->5）進行鬆弛。鬆弛完畢之後 dis 數組為：
繼續在剩下的 5 和 6 號頂點中，選出離 1 號頂點最近的頂點，這次選擇 5 號頂點。此時，dis[5]的值已經從「估計值」變為了「確定值」。對5號頂點的所有出邊（5->4）進行鬆弛。鬆弛完畢之後 dis 數組為：
最後對 6 號頂點的所有出邊進行鬆弛。因為這個例子中 6 號頂點沒有出邊，因此不用處理。 到此，dis 數組中所有的值都已經從「估計值」變為了「確定值」。
最終 dis 數組如下，這便是 1 號頂點到其餘各個頂點的最短路徑。
OK，現在來總結一下剛才的演算法。 Dijkstra演算法的基本思想是：每次找到離源點（上面例子的源點就是 1 號頂點）最近的一個頂點，然後以該頂點為中心進行擴展，最終得到源點到其餘所有點的最短路徑。
基本步驟如下：
在 博客 中看到兩個比較有趣的問題，也是在學習Dijkstra時，可能會有疑問的問題。
當我們看到上面這個圖的時候，憑借多年對平面幾何的學習，會發現在「三角形ABC」中，滿足不了 構成三角形的條件(任意兩邊之和大於第三邊)。 納尼，那為什麼圖中能那樣子畫？
還是「三角形ABC」，以A為起點，B為終點，如果按照平面幾何的知識， 「兩點之間線段最短」， 那麼，A到B的最短距離就應該是6(線段AB)，但是，實際上A到B的最短距離卻是3+2=5。這又怎麼解釋？
其實，之所以會有上面的疑問，是因為 對邊的權值和邊的長度這兩個概念的混淆， 。之所以這樣畫，也只是為了方便理解（每個人寫草稿的方式不同，你完全可以用別的方式表示，只要便於你理解即可）。
PS：數組實現鄰接表可能較難理解，可以看一下 這里
參考資料：
Dijkstra演算法是一種基於貪心策略的演算法。每次新擴展一個路程最短的點，更新與其相鄰的點的路程。當所有邊權都為正時，由於不會存在一個路程更短的沒擴展過的點，所以這個點的路程永遠不會再被改變，因而保證了演算法的正確性。
根據這個原理， 用Dijkstra演算法求最短路徑的圖不能有負權邊， 因為擴展到負權邊的時候會產生更短的路徑，有可能破壞了已經更新的點路徑不會發生改變的性質。
那麼，有沒有可以求帶負權邊的指定頂點到其餘各個頂點的最短路徑演算法（即「單源最短路徑」問題）呢？答案是有的， Bellman-Ford演算法 就是一種。（我們已經知道了 Floyd-Warshall 可以解決「多源最短路」問題，也要求圖的邊權均為正）
通過 鄰接矩陣 的Dijkstra時間復雜度是 。其中每次找到離 1 號頂點最近的頂點的時間復雜度是 O(N)，這里我們可以用 優先隊列（堆） 來優化，使得這一部分的時間復雜度降低到 。這個我們將在後面討論。
❸ 求鄰接矩陣任意兩點間的最短距離。matlab。程序在下面有沒有哪位大神能給解釋一下後邊的是什麼意思
根據lz要求，最合適的是floyd演算法
下面就是根據這個演算法寫的代碼，lz可以自己改成函數
D=[0 1 0 1 0 0
1 0 1 0 0 0
0 1 0 1 1 1
1 0 1 0 1 0
0 0 1 1 0 1
0 0 1 0 1 0];
n=length(D);
for k=1:n
for i=1:n
for j=1:n
if 0<D(i,k) & 0<D(k,j)
if D(i,j)==0 & i~=j
D(i,j)=D(i,k)+D(k,j);
else
D(i,j)=min(D(i,j),D(i,k)+D(k,j));
end
end
end
end
end
答案就儲存在D矩陣當中，這里
D =
0 1 2 1 2 3
1 0 1 2 2 2
2 1 0 1 1 1
1 2 1 0 1 2
2 2 1 1 0 1
3 2 1 2 1 0
演算法為O(n3)的，256^3=2^24 大概等於1600萬
效率上完全能夠忍受。
❹ 矩陣乘法求最短路徑
們把求A →E 的最短路分解為四個階段A →B →C→D →E 來求解.每一個階段可以用一個矩陣來表示,這個矩陣稱為權矩陣.相鄰階段的路徑可以用權矩陣的乘積來表示.但這里的矩陣乘法和普通矩陣乘積運算的區別是:普通矩陣乘積其對應元素是相應元素乘積的代數和,這里把元素相乘改為相加,元素的代數和改為取小運算,如果不同層節點間沒有連接,則視它們之間的距離為無窮大. 如果是求極大,改為取大運算,此時如果不同層節點間沒有連接,則視它們的距離為0.
如下：
由A地到B地的距離可表示為：A[2 5 8]
由B地到C地的權矩陣可表示為
[3,6,5；7,10,8；4,9,6]
因此由A到C的權矩陣為[2,5,8][3,6,5；7,10,8；4,9,6]＝[5,8,7]
因此由A到D的權矩陣為[5,8,7)][7,5；3,4；5,2]＝[11 ,9]
由A→E的權矩陣為：[11 ,9][4,2)]=[15,11]
因此從家裡到學校的最短距離為11百米,最近的路徑為從A地出發經過B1地C1地D2地到達E地.
下面我們給出基於「矩陣乘法」求解最短路的演算法:
第一階段:計算出圖中從起始點到終點最短路的長度.
step1 劃分出該網路圖中的層次關系(網路劃分為N 層,起點為第一層,終點為第N 層) ;
step2 依次給出從第i 層到第i + 1 層的權矩陣( i= 1 ,2 , …, N21) ; (若第i 層有m 個頂點;第i + 1 層有n
個頂點, 則從第i 層到第i + 1 層的權矩陣為m *n
階) .
step3 按照我們定義的矩陣乘法計算出最短路的
數值.
第二階段:尋找最短路所經過的中間點.
(利用第一階段中step2 的數據) 計算出從第i 層到
終點的最短路, 對比與i21 層到終點的最短路, 從而確
定出第i 層上最短路所經過的頂點( i = 2 , …, N21) .
❺ matlab實現floyd演算法 已知距離矩陣和權值矩陣 求最短路徑
希望可以幫到你。
function [D,path]=floyd(a)
n=size(a,1);
D=a;
path=zeros(n,n);
for i=1:n
for j=1:n
if D(i,j)~=inf
path(i,j)=j;
end
end
end
for k=1:n
for i=1:n
for j=1:n
if D(i,k)+D(k,j)<D(i,j)
D(i,j)=D(i,k)+D(k,j);
path(i,j)=path(i,k)
end
end
end
end
function [L,R]=router(D,path,s,t)
L=zeros(0,0);
R=s;
while 1
if s==t
L=fliplr(L);
L=[0,L];
return
end
L=[L,D(s,t)];
R=[R,path(s,t)];
s=path(s,t);
end
❻ 物流定量分析方法中的矩陣乘法和除法怎樣計算的
一些符號貼不上來，蛋卷給你矩陣乘法PPT下載地址吧,除法可以換算成乘法來算的，給你2個PPT下載地址，你好好復習一下，呵呵。【PPT】矩陣乘法 地址1: http://jw1.nwnu.e.cn/jpkc/jwc/2004jpkc/gdds/jxkj/5.ppt2次型矩陣乘法 地址2： http://course.cug.e.cn/cugFourth/gddsh/page/jxzy/05.ppt希望蛋卷的回答可以幫上你。
❼ 誰告訴我物流中的去線破圈法是怎樣的
配送路線三－破圈法下圖為是一張高速公路網路示意圖，其中A是起點，J是終點，B、C、D、E、G、H、I是網路上的節點，節點與節點之間以線路連接，線路上的數字表明了兩個節點之間的距離。求從起點A到終點J之間的最短運輸路線。解：用破圈法求解得最短路線為：A－B－E－I－J。最短運輸距離為90+90+84+126=390公里。圖中虛線表示破圈過程，即去掉的邊情形。粗實線表示最短路線。圖片參考地址： http://www.sina88.com/com/xdfpx/down/1100578578.doc 匈牙利法運演算法則： １先將欲指派工作之人員與將分派之工作或機器設備等，可能發生之成本（或可能產生之績效）列成相對應之方陣。 ２將方陣每列各數值減以各該列中之最小值。 ３再將每行中各數值減以各該行中之最小值。 ４盡可能以最少直線，縱線或橫線，劃去方陣中全部 若所劃直線數目與擬分派的工作項目或擬指派的人員數目，即方陣的行數或列數相等時，即已獲得最佳指派；否則，繼續進行下一步驟。 ５尋求方陣中未被劃線的最小數值，將所有未被劃線的各數減此最小數值，並將有直線相交的數字，加以此最小數值，其餘劃線的數值不變，然後在回到第四步驟求解。 例：某師師部有後勤官、訓練官、人事官、營務官四項職缺待分配，人事業管單位簽擬甲、乙、丙、丁四位軍官候選，雖然他們四人都可擔當這四項職務中的任意一項，但由於個人經歷、學歷、專長、性格特點等情況有差別，每個人擔任不同職務時效率都不一樣，人事科長於是用匈牙利法給每個人每項職務打分數如表所示 貴官為人事科長，應該如何分配這四個人工作？ 解： １將矩陣的每列減去該列最小元素，得表 ２將矩陣的每行減去該行最小元素，得表 ３用三條直線可劃去所有含有 的行或列，需繼續疊代，得表 ４用四條直線可劃去所有含 之行或列，即得最適解，得表 ５進行分派： 即甲─人事官；乙─營務官；丙─後勤官；丁─訓練官；從上述四位軍官分配的職務情況來看，甲、乙、丁是最大限度發揮專長，雖然丙沒有發揮其專長，但整體效益卻是最高的，其總分為４０＋３６＋３５＋４３＝１５４。
❽ 如何由鄰接矩陣求出距離矩陣
最簡單是用Floyd法,即是用動態規劃做道路鬆弛. 先將道路鄰接矩陣填入d(i,j).
過程:枚舉i,j,k:d(i,j)=min{d(i,k)+d(k,j)}
最後得到的d(i,j)就是距離.
❾ 數學建模 求最短距離 最好能用多種方法
用matlab解
%求A到E的最短距離
AB=[2 4 3];
BC=[7 4 6;3 2 4;4 1 5];
CD=[1 4;6 3;3 3];
DE=[3;4];
l=zeros(1,100)+1000;
n=1;
for a=1:3
L=AB(1,a);
for b=1:3
L=L+BC(a,b);
for c=1:2
L=L+CD(b,c)+DE(c,1);
l(1,n)=L;
n=n+1;
end
end
end
minL=min(l)
運行程序得到minL=11
數學模型
（Mathematical Model）是一種模擬，是用數學符號、數學式子、程序、圖形等對實際課題本質屬性的抽象而又簡潔的刻畫，它或能解釋某些客觀現象，或能預測未來的發展規律，或能為控制某一現象的發展提供某種意義下的最優策略或較好策略。
數學模型一般並非現實問題的直接翻版，它的建立常常既需要人們對現實問題深入細微的觀察和分析，又需要人們靈活巧妙地利用各種數學知識。
❿ 求教：蟻群演算法選擇最短路徑問題
這個例子其實是當初數模比賽時用來完成碎片拼接的，但其所用到原理還是求解最短路徑的原理。但這里的最短路徑和數據結構中最短路徑有一定的區別。在數據結構中，對於最短路徑的求解常用的一般有Dijkstra演算法與Floyd演算法，但對於要求出一條經過所有的點的並且要求路徑最短，這些演算法還是有一定的局限性的。而蟻群演算法則很好地滿足了這些條件。話說回來，很想吐槽一下網路流傳的一些蟻群演算法的例子，當初學習這個時候，身邊也沒有相關的書籍，只好到網上找例子。網上關於這個演算法源代碼的常見的有2個版本，都是出自博客，但是在例子都代碼是不完整的，缺失了一部分，但就是這樣的例子，居然流傳甚廣，我很好奇那些轉載這些源碼的人是否真的有去學習過這些，去調試過。當然，我下面的例子也是無法直接編譯通過的，因為涉及到圖像讀取處理等方面的東西，所以就只貼演算法代碼部分。但是對於這個問題蟻群演算法有一個比較大的缺點，就是收斂很慢，不過對於數量小的路徑，效果還是很好的。function bestqueue =aco1(nt,nc_max,m ,st, sd ,Alpha ,Beta ,Rho ,Q,gethead,getend)%參數解釋：%nt 路徑所經過的點的個數；%nc_max 迭代的次數；%m 螞蟻的個數；%st 起點序號；%sd 終點序號；%Alpha 信息素系數；�ta 啟發因子系數；%Rho 蒸發系數；% Q 信息量；%gethead getend 是用來求距離矩陣的，可根據實際情況修改
% nt = 209;%碎片個數full = zeros(nt,nt);tic;%初始化距離矩陣for i =1:nt for t = 1:nt if i ~= t full(i,t) = sum(abs(getend(:,i) - gethead(:,t))); else full(i,t) = inf; end endend% a =full(156,187)eta = 1./full;%啟發因子，取距離的倒數% eta% e = eta(4,2)tau = ones(nt,nt);%信息素矩陣% tabu = zeros(nt,nt);%禁忌矩陣，取螞蟻數量和碎片數量一致，以減少迭代次數nc =1;%初始化迭代次數;rbest=zeros(nc_max,nt);%各代最佳路線rbest(:,1) = (linspace(st,st,nc_max))';rbest(:,nt) =(linspace(sd,sd,nc_max))'; lbest=zeros(nc_max,1);%各代最佳路線的長度pathlen = 0;%臨時記錄每代最佳路線長度stime = 1;%記錄代數進度for i = 1:nc_max % 代數循環 delta_tau=zeros(nt,nt);%初始化改變數 stime for t = 1:m % 對螞蟻群體的循環， tabu=zeros(1,nt);%禁忌向量，標記已訪問的碎片，初試值設為0，訪問之後則變為1; viseted = zeros(1,nt);%記錄已訪問的元素的位置 tabu(st) = 1;%st為起點，在此表示為碎片矩陣的編號，因為已經將蟻群放在起點，故也應將禁忌向量和位置向量的狀態進行修改 tabu(sd) =1;%同上 visited(nt) = sd ;%同上； visited(1) = st;%同上； ht = 0; for r = 2:nt-1 %記錄了還沒訪問的圖片編號 vp = 1;%visited指示量 pp = [];%置空的概率向量 jc = 0; %獲取尚未訪問的位置的向量。 wv = zeros( nt -2 - ht ); for k =1 : nt if tabu(k) == 0 jc = jc +1; wv(jc) = k; end end% a =(tau(visited(end),ju(3))^Alpha)*(eta(visited(end),ju(3))^Beta)% visited(end) %計算選擇的概率 for k=1:length(wv) pp(k)=(tau(visited(vp),wv(k))^Alpha)*(eta(visited(vp),wv(k))^Beta);%下一張碎片的選擇概率計算，p =（信息素^信息素系數）*（啟發因子^啟發因子系數） end pp=pp./(sum(pp));%歸一化 pcum =cumsum(pp); psl = find(pcum >= rand);%輪盤賭法 to_visit= wv(psl(1)) ;%完成選點 tabu(to_visit) =1; visited(r) = to_visit; ht =ht +1;%已訪問碎片個數變化 vp =vp+1; end %路徑變化信息 %對單個螞蟻的路徑進行統計 sum1 =0; for pr = 1:nt -1 x = visited(pr); y = visited(pr+1) ; sum1 =sum1 + full(x,y); end% vcell{t} =visited;%元胞記錄每個螞蟻的路徑，即碎片順序;% msum(t) = sum1; %信息素變化； for ww=1:(nt-1) delta_tau(visited(ww),visited(ww+1))=delta_tau(visited(ww),visited(ww+1)) + Q/sum1; end% delta_tau(visited(end),visited(1))=delta_tau(visited(end),visited(1))+Q/(sum1/100);% if t == m & i == nc_max % bestqueue = visited% end if t == m bestqueue = visited end end tau=(1-Rho).*tau+delta_tau; %完成信息素的更新，找出現有的最新的最佳路徑,即信息素最多的路徑； stime =stime +1;end toc;