怎样用matlab编程实现Dijkstra算法

Dijkstra算法是寻找最短路径的一种搜索算法，由荷兰科学家提出。

算法描述：通过为每个节点保留目前为止所找到的从s到e的最短路径。为了记录最佳路径轨迹，记录路径上每个节点的前趋，通过回溯法找出最短路径轨迹。

在网上搜索一些版本的Matlab实现方法，感觉都有些毛病。经过修改，得到比较好的效果。

[cpp] view plain copy

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 copy

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 copy

[cpp] view plain copy

[distance,path]=Dijk(W,1,4);

>> distance

distance =

35

>> path

path =

1 6 4

从节点1到节点4最短距离路径为1-->6-->4, 最短距离为35

分类: 教育/科学 >> 学习帮助

问题描述:

这是我们的作业，可我不太会做，想找高手帮忙设计出这个程序。

有图，有数组，都是我自己弄的。

请好心人与我联系。

急！

谢谢！

先悬赏100，并补献全部积分，若成功还可有额外补助~

请高手速与我联系！

解析:

以下

输入时，将s,t,x,y,z五个点按照1,2,3,4,5起别名，输入格式按照下图例所示

当提示Please enter the vertex where Dijkstra algorithm starts:时输入算法的起始点

比如计算结果v1v4v2表示从点1到点2经过1，4，2为最短路径

Dijkstra算法的完整实现版本，算法的源代码

/ Dijkstrac

Copyright (c) 2002, 2006 by ctu_85

All Rights Reserved

/

#include "stdioh"

#include "malloch"

#define maxium 32767

#define maxver 9 /defines the max number of vertexs which the programm can handle/

#define OK 1

struct Point

{

char vertex[3];

struct Link work;

struct Point next;

};

struct Link

{

char vertex[3];

int value;

struct Link next;

};

struct Table /the workbannch of the algorithm/

{

int cost;

int Known;

char vertex[3];

char path[3];

struct Table next;

};

int Dijkstra(struct Point ,struct Table );

int PrintTable(int,struct Table );

int PrintPath(int,struct Table ,struct Table );

struct Table CreateTable(int,int);

struct Point FindSmallest(struct Table ,struct Point );/Find the vertex which has the allest value reside in the table/

int main()

{

int i,j,num,temp,val;

char c;

struct Point poinpre,poinhead,poin;

struct Link linpre,linhead,lin;

struct Table tabhead;

poinpre=poinhead=poin=(struct Point )malloc(sizeof(struct Point));

poin->next=NULL;

poin->work=NULL;

restart:

printf("Notice:if you wanna to input a vertex,you must use the format of number!\n");

printf("Please input the number of points:\n");

scanf("%d",&num);

if(num>maxver||num<1||num%1!=0)

{

printf("\nNumber of points exception!");

goto restart;

}

for(i=0;i<num;i++)

{

printf("Please input the points next to point %d,end with 0:\n",i+1);

poin=(struct Point )malloc(sizeof(struct Point));

poinpre->next=poin;

poin->vertex[0]='v';

poin->vertex[1]='0'+i+1;

poin->vertex[2]='\0';

linpre=lin=poin->work;

linpre->next=NULL;

for(j=0;j<num-1;j++)

{

printf("The number of the %d th vertex linked to vertex %d:",j+1,i+1);

scanf("%d",&temp);

if(temp==0)

{

lin->next=NULL;

break;

}

else

{

lin=(struct Link )malloc(sizeof(struct Link));

linpre->next=lin;

lin->vertex[0]='v';

lin->vertex[1]='0'+temp;

lin->vertex[2]='\0';

printf("Please input the value beixt %d th point towards %d th point:",i+1,temp);

scanf("%d",&val);

lin->value=val;

linpre=linpre->next;

lin->next=NULL;

}

}

poinpre=poinpre->next;

poin->next=NULL;

}

printf("Please enter the vertex where Dijkstra algorithm starts:\n");

scanf("%d",&temp);

tabhead=CreateTable(temp,num);

Dijkstra(poinhead,tabhead);

PrintTable(temp,tabhead);

return OK;

}

struct Table CreateTable(int vertex,int total)

{

struct Table head,pre,p;

int i;

head=pre=p=(struct Table )malloc(sizeof(struct Table));

p->next=NULL;

for(i=0;i<total;i++)

{

p=(struct Table )malloc(sizeof(struct Table));

pre->next=p;

if(i+1==vertex)

{

p->vertex[0]='v';

p->vertex[1]='0'+i+1;

p->vertex[2]='\0';

p->cost=0;

p->Known=0;

}

else

{

p->vertex[0]='v';

p->vertex[1]='0'+i+1;

p->vertex[2]='\0';

p->cost=maxium;

p->Known=0;

}

p->next=NULL;

pre=pre->next;

}

return head;

}

int Dijkstra(struct Point p1,struct Table p2) / Core of the programm/

{

int costs;

char temp;

struct Point poinhead=p1,now;

struct Link linna;

struct Table tabhead=p2,searc,result;

while(1)

{

now=FindSmallest(tabhead,poinhead);

if(now==NULL)

break;

result=p2;

result=result->next;

while(result!=NULL)

{

if(result->vertex[1]==now->vertex[1])

break;

else

result=result->next;

}

linna=now->work->next;

while(linna!=NULL) / update all the vertexs linked to the signed vertex/

{

temp=linna->vertex[1];

searc=tabhead->next;

while(searc!=NULL)

{

if(searc->vertex[1]==temp)/find the vertex linked to the signed vertex in the table and update/

{

if((result->cost+linna->value)<searc->cost)

{

searc->cost=result->cost+linna->value;/set the new value/

searc->path[0]='v';

searc->path[1]=now->vertex[1];

searc->path[2]='\0';

}

break;

}

else

searc=searc->next;

}

linna=linna->next;

}

}

return 1;

}

struct Point FindSmallest(struct Table head,struct Point poinhead)

{

struct Point result;

struct Table temp;

int min=maxium,status=0;

head=head->next;

poinhead=poinhead->next;

while(head!=NULL)

{

if(!head->Known&&head->cost<min)

{

min=head->cost;

result=poinhead;

temp=head;

status=1;

}

head=head->next;

poinhead=poinhead->next;

}

if(status)

{

temp->Known=1;

return result;

}

else

return NULL;

}

int PrintTable(int start,struct Table head)

{

struct Table begin=head;

head=head->next;

while(head!=NULL)

{

if((head->vertex[1]-'0')!=start)

PrintPath(start,head,begin);

head=head->next;

}

return OK;

}

int PrintPath(int start,struct Table head,struct Table begin)

{

struct Table temp=begin->next,p,t;

p=head;

t=begin;

if((p->vertex[1]-'0')!=start&&p!=NULL)

{

while(temp->vertex[1]!=p->path[1]&&temp!=NULL)

temp=temp->next;

PrintPath(start,temp,t);

printf("%s",p->vertex);

}

else

if(p!=NULL)

printf("\n%s",p->vertex);

return OK;

}

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); 100rand(2,10)]';

% segments = [(1:17); floor(1:05:9); ceil(2:05: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: 13

% 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 Lrand(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 < 06)

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_nodesrand); disp(['start id = ' num2str(start_id)]);

finish_id = ceil(num_nodesrand); 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

Dijkstra算法的思想是DP +贪婪。

每次寻找最近的点，扩大和更新的状态

为（i = 1; <N; + +）/ /扩展N-1

{

T =无穷大;

K = 1;

为（J = 1，J <N，J + +）/ /这里是为了找到最近的点，D最小< （/（[J]）&&（D [J] T [K]））

{

吨= D [J];

K =

}

[K] = 1 ;/ / k点加入的S

（J = 1，J <N，J + +）

（（！ [J]）&&（D [J]>的D [k] + W [K] [J]））/ /更新状态基于动态规划

{

D [J] =的D [k] + W [K] [J];

P [J] = K;

}

>}

不知道LZ在哪里目前还不清楚

给定 加权有向图 G=(V,E,W)，每条边的权值w为 非负数 ，表示两个顶点间的距离。

源点s∈V。

求：从s出发到其他各个顶点的最短路径。

如上图所示，以1为源点，计算到其余各个顶点的最短距离（我已用红线标出）。下面列出了最终解：

S集合 ：当从s到x（x ∈V ）的最短路径找到时，则x ∈S。当所有顶点都进入S集合时，算法结束。

初始：S=｛s｝，当S=V时算法结束。

从s到u相对于S的最短路径 ：指从s到u且仅经过S中顶点的最短路径。

dist[u]:从s到u相对于S的最短路径长度

short[u]:从s到u最短路径的长度（算法最终解）

dist[u] ≥ short[u]

Dijkstra算法采用贪心算法模式，算法过程就是通过计算dist[u],不断扩充S集合，同时dist[u]会不断优化改善，直到dist[u] = short[u]，并将其放到S中，当所有顶点都放入S集合时，算法结束。

输入：加权有向图G=(V,E,W)

          V={1,2,…,n}, s=1

输出：从s到每个顶点的最短路径

输入：G=(V,E,W)，源点1

          V={1,2,3,4,5,6}

初始S集合只有1，计算直接从1能到达的顶点的距离，其他不能从1号顶点直接到达的顶点都记为无穷大。此时从dist[u]里找出最短距离的顶点（6号），并将其放进S集合。

  S={1}

  dist[1] = 0

  dist[2] = 10

  dist[6 ] = 3

  dist[3] = ∞

  dist[4] = ∞

  dist[5] = ∞

当把6号顶点放进S集合后，经由6号顶点出发到达的顶点的最短距离可能会被优化更新，因为该算法的思想很“贪心”，谁更短我要谁！比如1->6->2要比1->2距离更短，所以dist[2]被更新为5，从专业术语上讲，这个“更新”过程叫做松弛，其他点同理。然后从dist[u]里找出最短的路径的那个顶点（5号），并放进S集合里。

  S={1,6}

  dist[1] = 0

 dist[6] = 3

  dist[2] = 5

  dist[4] = 9

  dist[5] = 4

  dist[3] = ∞

后面的 *** 作步骤其实就是重复上面的 *** 作。即当S集合里有个新的顶点后，就可能会更新其他点的最短距离，更新一遍后，找出当前最短距离的dist[u]，并将该顶点放进S集合。后面不重复阐述。

  S={1,6,5}

  dist[1] = 0

 dist[6] = 3

  dist[5] = 4

  dist[2] = 5

  dist[4] = 9

  dist[3] = ∞

  S={1,6,5,2}

  dist[1] = 0

 dist[6] = 3

  dist[5] = 4

 dist[2] = 5

  dist[4] = 9

  dist[3] = 12

  S={1,6,5,2,4}

  dist[1] = 0

 dist[6] = 3

  dist[5] = 4

 dist[2] = 5

 dist[4] = 9

  dist[3] = 12

  S={1,6,5,2,4,3}

  dist[1] = 0

 dist[6] = 3

  dist[5] = 4

 dist[2] = 5

 dist[4] = 9

 dist[3] = 12

当有向图中的所有顶点都进入了S集合后，算法结束，此时的dist[u]的值其实就是最初我们找出的那个最终解short[u]，所以，算法结束时，dist[u]=short[u],得到最终解。

以上就是关于怎样用matlab编程实现Dijkstra算法全部的内容，包括:怎样用matlab编程实现Dijkstra算法、怎样用DIJKSTRA算法设计最短路径、Dijkstra算法matlab如何应用等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！