dijkstra演算法matlab

1. Dijkstra演算法matlab如何應用

Matlab解法：
function [dist,path] = dijkstra(nodes,segments,start_id,finish_id)
%DIJKSTRA Calculates the shortest distance and path between points on a map
% using Dijkstra's Shortest Path Algorithm
%
% [DIST, PATH] = DIJKSTRA(NODES, SEGMENTS, SID, FID)
% Calculates the shortest distance and path between start and finish nodes SID and FID
%
% [DIST, PATH] = DIJKSTRA(NODES, SEGMENTS, SID)
% Calculates the shortest distances and paths from the starting node SID to all
% other nodes in the map
%
% Note:
% DIJKSTRA is set up so that an example is created if no inputs are provided,
% but ignores the example and just processes the inputs if they are given.
%
% Inputs:
% NODES should be an Nx3 or Nx4 matrix with the format [ID X Y] or [ID X Y Z]
% where ID is an integer, and X, Y, Z are cartesian position coordinates)
% SEGMENTS should be an Mx3 matrix with the format [ID N1 N2]
% where ID is an integer, and N1, N2 correspond to node IDs from NODES list
% such that there is an [undirected] edge/segment between node N1 and node N2
% SID should be an integer in the node ID list corresponding with the starting node
% FID (optional) should be an integer in the node ID list corresponding with the finish
%
% Outputs:
% DIST is the shortest Euclidean distance
% If FID was specified, DIST will be a 1x1 double representing the shortest
% Euclidean distance between SID and FID along the map segments. DIST will have
% a value of INF if there are no segments connecting SID and FID.
% If FID was not specified, DIST will be a 1xN vector representing the shortest
% Euclidean distance between SID and all other nodes on the map. DIST will have
% a value of INF for any nodes that cannot be reached along segments of the map.
% PATH is a list of nodes containing the shortest route
% If FID was specified, PATH will be a 1xP vector of node IDs from SID to FID.
% NAN will be returned if there are no segments connecting SID to FID.
% If FID was not specified, PATH will be a 1xN cell of vectors representing the
% shortest route from SID to all other nodes on the map. PATH will have a value
% of NAN for any nodes that cannot be reached along the segments of the map.
%
% Example:
% dijkstra; % calculates shortest path and distance between two nodes
% % on a map of randomly generated nodes and segments
%
% Example:
% nodes = [(1:10); 100*rand(2,10)]';
% segments = [(1:17); floor(1:0.5:9); ceil(2:0.5:10)]';
% figure; plot(nodes(:,2), nodes(:,3),'k.');
% hold on;
% for s = 1:17
% if (s <= 10) text(nodes(s,2),nodes(s,3),[' ' num2str(s)]); end
% plot(nodes(segments(s,2:3)',2),nodes(segments(s,2:3)',3),'k');
% end
% [d, p] = dijkstra(nodes, segments, 1, 10)
% for n = 2:length(p)
% plot(nodes(p(n-1:n),2),nodes(p(n-1:n),3),'r-.','linewidth',2);
% end
% hold off;
%
% Author: Joseph Kirk
% Email: jdkirk630 at gmail dot com
% Release: 1.3
% Release Date: 5/18/07
if (nargin < 3) % SETUP
% (GENERATE RANDOM EXAMPLE OF NODES AND SEGMENTS IF NOT GIVEN AS INPUTS)
% Create a random set of nodes/vertices,and connect some of them with
% edges/segments. Then graph the resulting map.
num_nodes = 40; L = 100; max_seg_length = 30; ids = (1:num_nodes)';
nodes = [ids L*rand(num_nodes,2)]; % create random nodes
h = figure; plot(nodes(:,2),nodes(:,3),'k.') % plot the nodes
text(nodes(num_nodes,2),nodes(num_nodes,3),...
[' ' num2str(ids(num_nodes))],'Color','b','FontWeight','b')
hold on
num_segs = 0; segments = zeros(num_nodes*(num_nodes-1)/2,3);
for i = 1:num_nodes-1 % create edges between some of the nodes
text(nodes(i,2),nodes(i,3),[' ' num2str(ids(i))],'Color','b','FontWeight','b')
for j = i+1:num_nodes
d = sqrt(sum((nodes(i,2:3) - nodes(j,2:3)).^2));
if and(d < max_seg_length,rand < 0.6)
plot([nodes(i,2) nodes(j,2)],[nodes(i,3) nodes(j,3)],'k.-')
% add this link to the segments list
num_segs = num_segs + 1;
segments(num_segs,:) = [num_segs nodes(i,1) nodes(j,1)];
end
end
end
segments(num_segs+1:num_nodes*(num_nodes-1)/2,:) = [];
axis([0 L 0 L])
% Calculate Shortest Path Using Dijkstra's Algorithm
% Get random starting/ending nodes,compute the shortest distance and path.
start_id = ceil(num_nodes*rand); disp(['start id = ' num2str(start_id)]);
finish_id = ceil(num_nodes*rand); disp(['finish id = ' num2str(finish_id)]);
[distance,path] = dijkstra(nodes,segments,start_id,finish_id);
disp(['distance = ' num2str(distance)]); disp(['path = [' num2str(path) ']']);
% If a Shortest Path exists,Plot it on the Map.
figure(h)
for k = 2:length(path)
m = find(nodes(:,1) == path(k-1));
n = find(nodes(:,1) == path(k));
plot([nodes(m,2) nodes(n,2)],[nodes(m,3) nodes(n,3)],'ro-','LineWidth',2);
end
title(['Shortest Distance from ' num2str(start_id) ' to ' ...
num2str(finish_id) ' = ' num2str(distance)])
hold off

else %--------------------------------------------------------------------------
% MAIN FUNCTION - DIJKSTRA'S ALGORITHM

% initializations
node_ids = nodes(:,1);
[num_map_pts,cols] = size(nodes);
table = sparse(num_map_pts,2);
shortest_distance = Inf(num_map_pts,1);
settled = zeros(num_map_pts,1);
path = num2cell(NaN(num_map_pts,1));
col = 2;
pidx = find(start_id == node_ids);
shortest_distance(pidx) = 0;
table(pidx,col) = 0;
settled(pidx) = 1;
path(pidx) = {start_id};
if (nargin < 4) % compute shortest path for all nodes
while_cmd = 'sum(~settled) > 0';
else % terminate algorithm early
while_cmd = 'settled(zz) == 0';
zz = find(finish_id == node_ids);
end
while eval(while_cmd)
% update the table
table(:,col-1) = table(:,col);
table(pidx,col) = 0;
% find neighboring nodes in the segments list
neighbor_ids = [segments(node_ids(pidx) == segments(:,2),3);
segments(node_ids(pidx) == segments(:,3),2)];
% calculate the distances to the neighboring nodes and keep track of the paths
for k = 1:length(neighbor_ids)
cidx = find(neighbor_ids(k) == node_ids);
if ~settled(cidx)
d = sqrt(sum((nodes(pidx,2:cols) - nodes(cidx,2:cols)).^2));
if (table(cidx,col-1) == 0) || ...
(table(cidx,col-1) > (table(pidx,col-1) + d))
table(cidx,col) = table(pidx,col-1) + d;
tmp_path = path(pidx);
path(cidx) = {[tmp_path{1} neighbor_ids(k)]};
else
table(cidx,col) = table(cidx,col-1);
end
end
end
% find the minimum non-zero value in the table and save it
nidx = find(table(:,col));
ndx = find(table(nidx,col) == min(table(nidx,col)));
if isempty(ndx)
break
else
pidx = nidx(ndx(1));
shortest_distance(pidx) = table(pidx,col);
settled(pidx) = 1;
end
end
if (nargin < 4) % return the distance and path arrays for all of the nodes
dist = shortest_distance';
path = path';
else % return the distance and path for the ending node
dist = shortest_distance(zz);
path = path(zz);
path = path{1};
end
end

2. dijkstra演算法在matlab上的問題

graphshortestpath是生物信息工具箱（Bioinformatics Toolbox）中的函數。MATLAB 7.0（R14）中包含的生物信息工具箱應該是1.1版，但graphshortestpath函數是2.4版才加入的新函數，對應的MATLAB版本是7.3（2006b）。
最好的解決辦法是安裝一個新版的MATLAB，因為往往一個工具箱中的函數調整會涉及到多個函數，如果繼續使用舊版，即使把這個函數傳給你，也十之八九不能使用。

我在另一個提問中的回答提供了MATLAB下載，供參考：
http://..com/question/577883207.html

順便說一句，很久很久以前我用過一段時間7.0，確信它存在比較嚴重的BUG，所以現在寧可用更早的6.5也不用7.0（但新一些的版本比如上面提供的兩個沒問題）。

3. dijkstra 的MATLAB演算法 最短路

9個客戶點，1個車場。需求與距離已給，完成車場到各客戶點及各個點對之間的最短路。假設運輸單價為1，根據需求和最短路計算運輸費用（我一直沒弄懂需求與最短路有什麼關系）。
已知的是各點的XY坐標與各點的需求（第一個點位車場，其餘9個點為客戶點，需求里第一個點不用管）
若出現距離小於10，在原距離基礎上加10
x=[8 12 14 16 4 2 8 8 9 10;]
y=[3 9 4 9 12 14 16 18 13 15;]
demand=[2 13 18 10 9 1 12 4 1 3;](第一個數不用管)
鄰接矩陣為
path_g =

0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 0 1 0 1 0 0
0 0 0 0 0 0 1 1 1 0
1 1 0 0 0 1 1 0 1 0
0 0 1 0 1 0 0 0 0 0
1 1 0 1 1 0 0 0 0 0
1 1 1 1 0 0 0 0 1 1
1 1 0 1 1 0 0 1 0 0
0 0 0 0 0 0 0 1 0 0
數據不重要，主要是方法！！！
發過去了

4. 關於Matlab Dijkstra演算法問題，麻煩幫我解釋下，謝謝。

第一步：設置初始點，S為已找到最短距離的點集，開始為初始點u0，L（v）為記錄各點到初始點u0的距離，設置默認到其他點距離為無窮，便於下面比較

第二步：對於每個不屬於S集合的點v，求取L（v），v到S集合中任意點u的距離W(uv)+L（u）中最小值，這個不難理解吧，就是有通過已經確認是最短路徑的點供你選擇，你不選么？

第三步：也就是搜索點是否結束的判斷，當S中包含所有點時，就可以停止搜索了，這里取i=V-1是因為 S默認已經有原點了，所以還有|V|-1個點需要判斷加入到S中

下面給你個實現程序，很久之前寫的，是個函數，放在Dijkstra.m文件中，直接調用即可，w為輸入矩陣，也就是網路點陣：
% Dijkstra Solution Steps
function [l,z]=Dijkstra(w)
n=size(w,1);
% 賦初值
for i=1:n
l(i)=w(1,i);
z(i)=1;
end
%s為每次搜索到非S中的點到u點的最短距離集合
s=[];
s(1)=1;
u=s(1);
k=1;
%搜索循環運算
while k<n
%找出以u為中間點，L中各點的最短路，初始點除外
for i=2:n
for j=1:k
if i~=s(j)&l(i)>l(u)+w(u,i)
l(i)=l(u)+w(u,i);
z(i)=u;
end
end
end
%找出非S點中到u點最短路的點v
ll=l;
lv=inf;
for i=2:n
c=find(i==s);
if isempty(c)&ll(i)<lv
lv=l(i);
v=i;
end
end
k=k+1;
s(k)=v;
u=s(k);
end

5. 怎樣用matlab編程實現Dijkstra演算法

Dijkstra演算法是尋找最短路徑的一種搜索演算法，由荷蘭科學家提出。
演算法描述：通過為每個節點保留目前為止所找到的從s到e的最短路徑。為了記錄最佳路徑軌跡，記錄路徑上每個節點的前趨，通過回溯法找出最短路徑軌跡。

在網上搜索一些版本的Matlab實現方法，感覺都有些毛病。經過修改，得到比較好的效果。

[cpp] view plain
function [ distance path] = Dijk( W,st,e )
%DIJK Summary of this function goes here
% W 權值矩陣 st 搜索的起點 e 搜索的終點
n=length(W);%節點數
D = W(st,:);
visit= ones(1:n); visit(st)=0;
parent = zeros(1,n);%記錄每個節點的上一個節點

path =[];

for i=1:n-1
temp = [];
%從起點出發，找最短距離的下一個點，每次不會重復原來的軌跡，設置visit判斷節點是否訪問
for j=1:n
if visit(j)
temp =[temp D(j)];
else
temp =[temp inf];
end

end

[value,index] = min(temp);

visit(index) = 0;

%更新 如果經過index節點，從起點到每個節點的路徑長度更小，則更新，記錄前趨節點，方便後面回溯循跡
for k=1:n
if D(k)>D(index)+W(index,k)
D(k) = D(index)+W(index,k);
parent(k) = index;
end
end

end

distance = D(e);%最短距離
%回溯法 從尾部往前尋找搜索路徑
t = e;
while t~=st && t>0
path =[t,path];
p=parent(t);t=p;
end
path =[st,path];%最短路徑

end

測試：
測試用例1

[cpp] view plain
W=[0 50 inf 40 25 10
50 0 15 20 inf 25
inf 15 0 10 20 inf
40 20 10 0 10 25
25 inf 20 10 0 55
10 25 inf 25 55 0];
[cpp] view plain

[cpp] view plain
[distance,path]=Dijk(W,1,4);
>> distance

distance =

35

>> path

path =

1 6 4

從節點1到節點4最短距離路徑為1-->6-->4, 最短距離為35

6. 關於matlab中的一個Dijkstra演算法應用

這個演算法算起始點到其他點的最短路徑。
function [d,index1,index2]=Dijkf(a)
%兩點間最短距離的Dijkstra演算法
% a表示圖的權值矩陣
% d表示所求最短路的權和
% index1 表示標號頂點的順序
% index2 表示標號頂點索引
% 起始點為第一個點
%參數初始化
M=max(max(a));
pb(1:length(a))=0;
pb(1)=1;
index1=1;
index2=ones(1:length(a));
d(1:length(a))=M;
d(1)=0;
temp=1;
%更新l（v），同時記錄頂點順序和頂點索引
while sum(pb)<length(a)
tb=find(pb==0); %第i次循環處理第i+1個頂點
d(tb)=min(d(tb),d(temp)+a(temp,tb)); %更新l（v）
tmpb=find(d(tb)==min(d(tb)));
temp=tb(tmpb(1));
pb(temp)=1;
index1=[index1,temp]; %記錄標號順序
index=index1(find(d(index1)==d(temp)-a(temp,index1)));
if length(index)>=2
index=index(1);
end
index2(temp)=index; %記錄標號索引
end

下面這個用來求任意兩點間的最短距離，還能算出路線。
function [P,u]=n2shorf(W,k1,k2)
%求任意兩點最短路徑演算法
% P 為兩點k1,k2間的最短路，頂點以經過次序進行排序
% u 為最短路的長度
% 初始化
n=length(W);
U=W;
m=1;
% 利用求最短路的Floyd演算法，求最短路矩陣
while m<=n
for i=1:n
for j=1:n
if U(i,j)>U(i,m)+U(m,j)
U(i,j)=U(i,m)+U(m,j);
end
end
end
m=m+1;
end
u=U(k1,k2);%最短距離
% 求任意給定兩個頂點見的最短路包含的頂點
P1=zeros(1,n);
k=1;
P1(k)=k2;
V=ones(1,n)*inf;
kk=k2;
while kk~=k1
for i=1:n
V(1,i)=U(k1,kk)-W(i,kk);
if V(1,i)==U(k1,i)
P1(k+1)=i;
kk=i;
k=k+1;
end
end
end
k=1;
wrow=find(P1~=0);
for j=length(wrow):(-1):1
P(k)=P1(wrow(j));
k=k+1;
end
end

7. dijkstra演算法的matlab實現 有些地方看不懂求大神

對呀，在上面的注釋中已經說明了a是權值矩陣，所以輸入的必須是矩陣

8. 圖論最短路問題的Dijkstra演算法與Matlab程序

這個Dijkstra演算法，matlab有自帶的graphshortestpath函數，直接調用即可。我將這個演算法給寫了個更直觀的BestRoad函數，你直接調用即可,具體調用格式如下：。

>>BestRoad
請輸入各個路徑的起始節點
ab=[1,1,1,1,1,2,2,2,2,3,3,3,4,4,5]
請輸入各個路徑的終止節點
bb=[2,3,4,5,6,3,4,5,6,4,5,6,5,6,6]
請輸入各個路徑的權值
w=[12,19,28,40,59,13,20,29,41,14,21,30,15,12,15]
請輸入起始節點
Begin=1
請輸入終止節點
End=6
是否為等權無向圖，0=>NO，1=>YES
dir=0
.

d=

40


p=

146

結果d是最優值，p是最優路徑。

9. 請教matlab Dijkstra演算法問題！

你的問題還應該是ndd=1的地方，當ndd=1時 循環：
for k=2:ndd
[tmp1,jj]=min(dd(1,k)+W(dd(2,k),V));
tmp2=V(jj);
tt(k-1,:)=[tmp1,tmp2,jj];
end
不運算，跳過。當ndd >=2開始運算。
[tmp1,jj]=min(dd(1,k)+W(dd(2,k),V));
tmp1和jj分別為後面數組的最小值和最小值對應的位置；
tmp2=V(jj);
tmp2賦值為V中jj位置的值；
tt(k-1,:)=[tmp1,tmp2,jj];
將tmp1,tmp2,jj賦值給tt的k-1行

10. 求各位高手Matlab dijkstra 演算法的使用方法。

我是搞建模的，這是圖論里求単源最短路徑（dijkstra ），你把其中的矩陣A，換成你要的D，就可以啦。
function [l,t]=dijkstra(A,v)
%dijkstra最短路演算法,某個頂點v到其餘頂點的最短路
% 例：A=[0 2 8 1 inf inf inf inf
%2 0 6 inf 1 inf inf inf
% 8 6 0 7 5 1 2 inf
% 1 inf 7 0 inf inf 9 inf
% inf 1 5 inf 0 3 inf 8
% inf inf 1 inf 3 0 4 6
% inf inf 2 9 inf 4 0 3
% inf inf inf inf 8 6 3 0];
n=length(A);%頂點個數
V=1:n;%頂點集合
s=v;%已經找到最短路的點集，初始為v
l=A(v,:);%當前v點到各個點的距離，初始為直接距離
t=v.*ones(1,n);%當前距離時點的父頂點，初始都為v
ss=setdiff(V,s);nn=length(ss);%還沒有找到最短路的點集
for j=1:n-1%一共進行n-1次迭代
k=ss(1);
for i=1:nn%對還沒有找到最短路的點
if l(k)>l(ss(i))
k=ss(i);
l(k)=l(ss(i));%在當前一行距離中取最小值
end
end
if l(k)==inf%如果當前行最小值是無窮大，則結束
break;
else%否則k點的最短路找到
s=union(s,k);
ss=setdiff(V,s);
nn=length(ss);
end
if length(s)==n%全部點的最短路都找到
break;
else
for i=1:nn%以k為生長點，如果通過k點會更短，則更改當前最短距離
if l(ss(i))>l(k)+A(k,ss(i))
l(ss(i))=l(k)+A(k,ss(i));
t(ss(i))=k;
end
end
end
end
%附：運行上面程序後，如果想更清楚的觀看點v到點vv的最短距離與路徑可用下面小程序：
% v=3;%v要與上面的v一致
% vv=4;k=vv;tt=vv;
% while(1)
% if k==v
% tt %路徑vv <--...<-- v
% l(vv) %距離
% break;
% else
% k=t(k);
% tt=[tt,k];
% end
%end