QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2442|回复: 0
打印 上一主题 下一主题

图中最短路径解决方法 Dijkstra

[复制链接]
字体大小: 正常 放大

1189

主题

4

听众

2934

积分

该用户从未签到

跳转到指定楼层
1#
发表于 2023-12-22 11:02 |只看该作者 |正序浏览
|招呼Ta 关注Ta
这段代码是Dijkstra算法的一个实现,用于在带权图中找到从一个起始点到其他所有点的最短路径。下面是对代码的逐步解释:5 n' ?$ k$ y" E& ]* s( t0 x3 e
clear all. l+ u& ~: u, H" t
%图论最短路问题的Dijkstra算法2 z/ `' w  Z( D+ j+ t4 x" R- l* \1 ]
%邻接矩阵(点与点的关系)
9 i+ |" Q9 K7 {; Y, L& K; l. F( ^w=[0,2,4,inf,inf,inf,inf;  # @$ @- _# m" X
   2,0,inf,3,3,1,inf;$ e5 _  k4 @! @! t
   4,inf,0,2,3,1,inf;                     
$ H$ h) V5 Y) F9 X* _   inf,3,2,0,inf,inf,1;                    ' C# G# `) {/ F
   inf,3,3,inf,0,inf,3;: |* M3 W1 R* C0 n0 C* d& u7 s! f
   inf,1,1,inf,inf,0,4;
$ X4 K: t$ O$ a+ t; o$ H   inf,inf,inf,1,3,4,0];; b& ]- W; ~2 |
n=size(w,1);%记录图中点数
8 z: [% w$ A2 a# y% n0 I3 h1 s4 r; {
for i=1:n. |* N: e) x9 i8 L& N
    l(i)=w(1,i); %为l(v)赋初值
. |7 f' x, u) U* M    z(i)=1;      %为z(v)赋初值1
7 ^$ X2 t/ E- {; `end
% f( J# v/ Q4 v; R) m
  ^3 [0 k* n8 R2 U* fs=[];            %s集合8 X8 C2 x: g/ t1 l: i
s(1)=1;          %s集合的第1个元素为起点0 I" \' o) T4 m3 ]/ p/ y( i
u=s(1);! s1 C' B6 B+ ?
k=1;             %k记录集合s中点的数量9 n6 C+ z: A# u# x0 p8 O% K
2 H  w. J! N2 S; A( e
while k<n       %当集合s未包含所有元素的时候执行循环
5 ?- x% m: m4 d# F$ }/ n* o/ @    for i=1:n    %更新一遍l(v),z(v)7 t* N# _- V% [& |) E% s- ^" F
        if l(i)>l(u)+w(u,i)
% X) b( c; ]4 B* f  ~% c            l(i)=l(u)+w(u,i);
, L% }" E9 ^# X" M            z(i)=u;* s$ f$ t% K2 ^, _9 s+ W
        end1 P; [& q. {1 B5 G
    end
8 W5 \+ Y4 g7 ~0 I) f; \% [6 S3 m  R5 J+ F
    %找l(i)中最小的v加入s集合4 k; w9 D+ h# R! _1 Y
    ll=l;9 \, |, X0 e( M! B3 z  K1 z! C, {8 l
    for i=1:n
" X& r9 k) k& D- b! x) o' K2 r        for j=1:k
* H5 r- d0 B6 F            if i==s(j). G  S& i% }( s/ p
                ll(i)=inf; %去除掉已经在s集合中的点
' ^& n% i( U: w4 }            end
, u; w/ y# N% ^$ C- c1 r$ O        end7 r% L6 S3 F* @) y. ~
    end
; h$ @' S8 ~0 J! ^, Z% E5 P0 O    [lv,v]=min(ll); %求最小的l(v)
; U6 W  R' d; p7 T; k  t( O6 v    s(k+1)=v;       %加入集合s2 \: J* W# O! f" X. O
    u=v;3 S$ Q  h3 g3 Y, x" R( q
    k=k+1;
5 M+ l9 ?3 h* o7 ~end
! g+ a- q$ M. e: I3 K* b
3 X) j: Q; h7 X3 s: Q# v4 X4 n; Kfprintf('最短路为:%1d->%1d->%1d->%1d\n',z(z(z(7))),z(z(7)),z(7),7)8 O6 |2 S* j$ o: v. w' r0 o0 z# @

7 w3 M4 h5 E& L6 U% O# F4 [+ @! K解释:
* o0 |! X7 q  ]
; M1 \  _: C) m* A, N1.清除变量: clear all 语句清除所有之前定义的变量,以确保从干净的状态开始执行程序。  p, o$ X! I& D* X/ k9 W5 t$ E" {
2.邻接矩阵: 图被表示为邻接矩阵 w,其中 w(i, j) 表示从顶点 i 到顶点 j 的边的权重。 inf 表示没有直接的边。
$ U: B. x0 ?* I: u! @3.初始化: l 数组存储从起始点到每个点的当前最短路径长度,z 数组存储路径中的前一个顶点。初始时,将起始点到每个点的距离初始化,并将前一个顶点初始化为起始点。
/ C( e$ [: H: r4 P9 }4 e  t4.主循环: 使用 while 循环,每次选择一个新的顶点加入集合 s,直到 s 包含所有顶点。在每次循环中,通过更新 l 和 z 数组来逐步找到最短路径。
/ R) l- d# D+ k/ N. s9 p5.输出: 最后,使用 fprintf 打印从起始点到指定点的最短路径。在这里,路径是通过回溯 z 数组得到的。, {; u- P$ l& n' Z( e2 I
# `7 W. e$ W. a9 [5 U
注意:这段代码的输出是针对特定的终点(顶点7)进行的,你可能需要根据你的需求更改这个值。3 N% a1 I8 E. h' j2 p
" q8 F1 k1 u) i4 z- ]. S' h0 u

% k2 L; b+ J6 H! T/ i

Dijkstra.m

913 Bytes, 下载次数: 0, 下载积分: 体力 -2 点

售价: 1 点体力  [记录]  [购买]

zan
转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
您需要登录后才可以回帖 登录 | 注册地址

qq
收缩
  • 电话咨询

  • 04714969085
fastpost

关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

手机版|Archiver| |繁體中文 手机客户端  

蒙公网安备 15010502000194号

Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

GMT+8, 2026-6-17 03:41 , Processed in 0.449014 second(s), 55 queries .

回顶部