dijkstra算法原理及MATLAB代码.pdfVIP

Dijkstra 算法是寻找最短路径的一种有哪些信誉好的足球投注网站算法，由荷兰科学家提出。 1) 算法思想：设 G=(V,E) 是一个带权有向图，把图中顶点集合 V 分成两组， 第一组为已求 出最短路径的顶点集合 （用S 表示，初始时 S 中只有一个源点， 以后每求得一条最短路径 , 就将加入到集合 S 中，直到全部顶点都加入到 S 中，算法就结束了）， 第二组为其余未确 定最短路径的顶点集合（用 U 表示）， 按最短路径长度的递增次序依次把第二组的顶点加 入 S 中。在加入的过程中，总保持从 源点 v 到 S 中各顶点的最短路径长度不大于从源点 v 到 U 中任何顶点的最短路径长度 。此外，每个顶点对应一个距离， S 中的顶点的距离就是 从 v 到此顶点的最短路径长度， U 中的顶点的距离，是从 v 到此顶点只包括 S 中的顶点为 中间顶点的当前最短路径长度。 2) 算法步骤： a. 初始时， S 只包含源点 ，即 S ＝{v} ，v 的距离为 0 。U 包含除 v 外的其他顶点， 即:U={ 其余顶点 } ，若 v 与 U 中顶点 u 有边，则 u,v 正常有权值，若 u 不是 v 的 出边邻接点，则 u,v 权值为 ∞ 。 b. 从 U 中选取一个距离 v 最小的顶点 k ，把 k ，加入 S 中（该选定的距离就是 v 到 k 的最短路径长度）。 c. 以 k 为新考虑的中间点，修改 U 中各顶点的距离；若从源点 v 到顶点 u 的距离（经 过顶点 k ）比原来距离（不经过顶点 k ）短，则修改顶点 u 的距离值，修改后的距离值 的顶点 k 的距离加上边上的权。 d. 重复步骤 b 和 c 直到所有顶点都包含在 S 中。 算法描述：通过为每个节点保留目前为止所找到的从 s 到 e 的最短路径。为了记录最佳路 径轨迹，记录路径上每个节点的前趋，通过回溯法找出最短路径轨迹。 过程如下： 在网上有哪些信誉好的足球投注网站一些版本的 Matlab 实现方法， 感觉都有些毛病。 经过修改， 得到比较好的效果。 [cpp] view plain copy 1. function [ distance path] = Dijk( W,st,e ) 2. %DIJK Summary of this function goes here 3. % W 权值矩阵 st 有哪些信誉好的足球投注网站的起点 e 有哪些信誉好的足球投注网站的终点 4. n=length(W);% 节点数 5. D = W(st,:); 6. visit= ones(1:n); visit(st)=0; 7. parent = zeros(1,n);% 记录每个节点的上一个节点 8. 9. path =[]; 10. 11. for i=1:n-1 12. temp = []; 13. % 从起点出发，找最短距离的下一个点，每次不会重复原来的轨迹，设置 visit 判断节点是 否访问 14. for j=1:n 15. if visit(j) 16. temp =[temp D(j)]; 17. else 18. temp =[temp inf];