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