＃i nclude <stdlib.h>
//Dijkstra算法实现函数
void Dijkstra(int n,int v,int dist[],int prev[],int **cost)
{
int i
int j
int maxint = 65535//定义一个最大的数值，作为不相连的两个节点的代价权值
s = (int *)malloc(sizeof(int) * n)
//初始化最小路径代价和前一跳节点值
for (i = 1i <= ni++)
{
dist[i] = cost[v][i]
s[i] = 0
if (dist[i] == maxint)
{
prev[i] = 0
}
else
{
prev[i] = v
}
}
dist[v] = 0
s[v] = 1//源节点作为最初的s子集
for (i = 1i <ni++)
{
int temp = maxint
int u = v
//加入具有最小代价的邻居节点到s子集
for (j = 1j <= nj++)
{
if ((!s[j]) &&(dist[j] <temp))
{
u = j
temp = dist[j]
}
}
s[u] = 1
//计算加入新的节点后，更新路径使得其产生代价最短
for (j = 1j <= nj++)
{
if ((!s[j]) &&(cost[u][j] <maxint))
{
int newdist = dist[u] + cost[u][j]
if (newdist <dist[j])
{
dist[j] = newdist
prev[j] = u
}
}
}
}
}
//展示最佳路径函数
void ShowPath(int n,int v,int u,int *dist,int *prev)
{
int j = 0
int w = u
int count = 0
int *way
way=(int *)malloc(sizeof(int)*(n+1))
//回溯路径
while (w != v)
{
count++
way[count] = prev[w]
w = prev[w]
}
//输出路径
printf("the best path is:\n")
for (j = countj >= 1j--)
{
printf("%d ->",way[j])
}
printf("%d\n",u)
}
//主函数，主要做输入输出工作
void main()
{
int i,j,t
int n,v,u
int **cost//代价矩阵
int *dist//最短路径代价
int *prev//前一跳节点空间
printf("please input the node number: ")
scanf("%d",&n)
printf("please input the cost status:\n")
cost=(int **)malloc(sizeof(int)*(n+1))
for (i = 1i <= ni++)
{
cost[i]=(int *)malloc(sizeof(int)*(n+1))
}
//输入代价矩阵
for (j = 1j <= nj++)
{
for (t = 1t <= nt++)
{
scanf("%d",&cost[j][t])
}
}
dist = (int *)malloc(sizeof(int)*n)
prev = (int *)malloc(sizeof(int)*n)
printf("please input the source node: ")
scanf("%d",&v)
//调用dijkstra算法
Dijkstra(n, v, dist, prev, cost)
printf("*****************************\n")
printf("have confirm the best path\n")
printf("*****************************\n")
for(i = 1i <= n i++)
{
if(i!=v)
{
printf("the distance cost from node %d to node %d is %d\n",v,i,dist[i])
printf("the pre-node of node %d is node %d \n",i,prev[i])
ShowPath(n,v,i, dist, prev)
}
}
}
function R=main_Dj()clcclear
G=[1 2 51 4 12 3 12 4 62 5 5.82 6 5.72 7 5.63 7 2 3 11 1.5 3 12 4...
4 5 0.54 8 3 5 6 15 9 36 7 0.66 10 2.5 7 11 2.78 9 18 12 6...
9 10 1.59 12 510 11 0.510 12 411 12 3]
opt=0
route=sroute(G,opt)
R=[]
r=route(3,end)
R=[r,R]
while r~=1
r=route(3,r)
R=[r,R]
end
R=char(R+64)
R=[R,'O']
end
function route=sroute(G,opt)
% 求图的最短路的Dijkstra算法，规定1是起点
% G是给定图的邻接矩阵或弧表矩阵，程序能够自动识别
% 当opt=0（或缺省）时求无向图的最短路，opt=1时求有向图的最短路
% d——标记最短距离
% route是一个矩阵，第一行标记顶点，第2行标记1到该点的最短距离，
% 第3行标记最短路上该点的先驱顶点
if (nargin==1) opt=0 end
while 1 % 此循环自动识别或由弧表矩阵生成邻接矩阵
if G(1,1)==0
A=G
n=size(A,1)
M=sum(sum(A))break
else
e=G
n=max([e(:,1)e(:,2)]) % 顶点数
m=size(e,1) % 边数
M=sum(e(:,3)) % 代表无穷大
A=M*ones(n,n)
for k=1:m
A(e(k,1),e(k,2))=e(k,3)
if opt==0
A(e(k,2),e(k,1))=e(k,3) % 形成无向图的邻接矩阵
end
end
A=A-M*eye(n) % 形成图的邻接矩阵
end
break
end
pb(1:length(A))=0pb(1)=1 % 永久标号点记为1
index1=1 % 依次记录永久标号顶点
index2=ones(1,length(A)) % 标记最短路上各点的先驱顶点
d(1:length(A))=Md(1)=0 % 标记距离
temp=1 % 标记最近一个永久标号点
while sum(pb)<length(A)
tb=find(pb==0) % 找出临时标号点
d(tb)=min(d(tb),d(temp)+A(temp,tb)) % 更新距离
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(index1,temp)')) % 确定前驱顶点
if length(index)>=2 % 前驱顶点多于1个时取第一个
index=index(1)
end
index2(temp)=index % 记录前驱顶点
end
route=[1:n d index2]
end
运行结果
R =
ADEFJKO
代码自己看，不解释，也别叫我解释了，很麻烦的。
开始，运行（或者直接按Win+R），输入notepad将下面两行百分号之间的内容复制进去，再保存成dijkstra.m，注意保存路径（最好保存到Matlab的工作路径中）
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [d,DD]=dijkstra(D,s)
%Dijkstra最短路算法Matlab程序用于求从起始点s到其它各点的最短路
%D为赋权邻接矩阵
%d为s到其它各点最短路径的长度
%DD记载了最短路径生成树
[m,n]=size(D)
d=inf.*ones(1,m)
d(1,s)=0
dd=zeros(1,m)
dd(1,s)=1
y=s
DD=zeros(m,m)
DD(y,y)=1
counter=1
while length(find(dd==1))<m
for i=1:m
if dd(i)==0
d(i)=min(d(i),d(y)+D(y,i))
end
end
ddd=inf
for i=1:m
if dd(i)==0&&d(i)<ddd
ddd=d(i)
end
end
yy=find(d==ddd)
counter=counter+1
DD(y,yy(1,1))=counter
DD(yy(1,1),y)=counter
y=yy(1,1)
dd(1,y)=1
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
然后在matlab命令窗口中，生成D和s
然后调用：[d,DD]=dijkstra(D,s)
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）