Floyd最短路径算法(2)

算法维护两个顶点集S和Q。集合S保留了我们已知的所有d[v]的值已经是最短路径的值顶点，而集合Q则保留其他所有顶点。集合S初始状态为空，而后每一步都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的d值的顶点。当一个顶点u从Q中转移到了S中，算法对每条外接边(u,v)进行拓展。 在下面的算法中,u:=Extract_Min(Q)在在顶点集Q中搜索有最小的d值的顶点u。这个顶点被从集合Q中删除并返回给用户。 1 function Dijkstra(G, w, s)

2 for each vertex v in V[G] // 初始化 3 d[v] := infinity

4 previous[v] := undefined 5 d[s] := 0

6 S := empty set

7 Q := set of all vertices

8 while Q is not an empty set // Dijstra算法主体 9 u := Extract_Min(Q) 10 S := S union {u}

11 for each edge (u,v) outgoing from u

12 if d[v] > d + w(u,v) // 拓展边(u,v) 13 d[v] := d + w(u,v) 14 previous[v] := u

如果我们只对在s和t之间寻找一条最短路径的话，我们可以在第9行添加条件如果满足u=t的话终止程序。

现在我们可以通过迭代来回溯出s到t的最短路径 1 S := empty sequence 2 u := t

3 while defined u 4 insert u to the beginning of S 5 u := previous

现在序列S就是从s到t的最短路径的顶点集. 本人自己写的蚁群算法。完全能够实现功能，就是收敛速度感觉有点慢。 % function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACO(C,D,s,e,NC_max,m,Alpha,Beta,Rho,Q) % function [Shortest_Route,Shortest_Length]=ACOR(C,D,s,e,NC_max,m,Alpha,Beta,Rho,Q)

%%========================================================================= %% ACO.m

%% Ant Colony Optimization Algorithm for Road Select Problem

%% LiLixin,ShenYang Insitute of Aeronautical engineering ,ShenYang,China %% Email:myassist@163.com %% All rights reserved

%%------------------------------------------------------------------------- %% 主要符号说明

%% C n个城市的坐标，n×2的矩阵

%% D 道路连通加权矩阵 %% s 起点 %% e 终点

%% NC_max 最大迭代次数 %% m 蚂蚁个数

%% Alpha 表征信息素重要程度的参数 %% Beta 表征启发式因子重要程度的参数 %% Rho 信息素蒸发系数 %% Q 信息素增加强度系数 %% R_best 各代最佳路线

%% L_best 各代最佳路线的长度

%%========================================================================= % clc clear

% 设置初始参数如下：

m=10;Alpha=1;Beta=5;Rho=0.1;NC_max=100;Q=100; %设定起始点 s=1;e=50;

% 31城市坐标为： C=[601.6 971.7 988.8 482.6 54.4 549.6 95.4 868 529.1 429.5 982 350.5 654.3 23.2 738.1 372 538.9 593.7 560.1 850.3 229.2 805.9 411.2 710 83.2 706.2 937.4 800.5 11.9 994.4 694.1 809.1 795.4 758.8 338.9 148.1 955.8 643.8 345.7 726.2 550.3 349.6 183.7 935.1 640 544 854.6 842.4 199.3 547.9 434.1 921.4

405.5 624.2 272.3 998.1 772 24.4 385.2 327.4 320.3 410.4 890 90 810 580 180 80 185 300 950 200 850 258.6 50 450 150 402 345 900 450 800 621 700 564.3 180 80.5 280 750 950 450 500 300 50 900 530 300 520 152 189.6 ];

D=[0 0 0 0 0 0 0 0 0 76.92 0 0 0 0 0 230.95 0 0 0 0 0 0 0 0 0 76.894 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 157.34 0 0 0 0 0

0 0 0 0 0 140.78 0 325.12 0 0 0 0 0 0 0 0 0

0 155.71 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 76.913 0 0

0 0 0 0 0 0 0 0 0 0 0 0 74.247 0 0 0 0 0 0 0 0 0 0 0 55.603 0

0 0 0 0 0 0 0 0 0 0 0 76.921 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 147.8 0 76.551 0 76.908 0 0

0 0 0 0 79.548 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 84.189 0 0 0 0 0 0 0 0 166.74 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 76.915 0 0 0 0

0 140.78 0 0 0 0 0 211.43 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 76.91 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 205.65 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 76.91

0 0 0 0 0 0 0 0 0 0 0 0 0 76.901 0 0 0 156.87 0 0 0

0 325.12 0 0 0 211.43 205.65 0 0 0 0 0 0 0 0 0 0 0 0 0 79.979 0 258.19 0 0 0 0 0 0 0 0 0 0 0 0 0 73.841 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 76.898 0 0 0 0 0 0 0 0 0 0 79.382 0 0 0

75.438 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

76.92 0 0 0 0 0 0 0 0 0 0 0 0 0 0 80.01 0 0 0 0 0 0 0 0 0 79.064 0 0 0 0 0 0 0 0 0 0 0 0 0 0 76.919 0 0 0 0 0 0 0 0 0

0 0 0 147.8 0 0 0 0 0 0 0 0 147.14 0 0 0 0 0 0 163.89 0 60.464 0 0 0 0 0 151.26 0 0 0 0 0 0

0 0 0 0 0 76.852 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 76.898 0 0 0 0 0 0 0 0 0 0 76.922 0 0 0 0 0 0

81.004 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 74.247 76.551 0 0 0 0 0 0 147.14 0 0 0 0 0 0 0 0 0 0 0 0 0 155.58 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 79.124 0 79.49

0 0 0 0 76.899 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 76.908 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 76.889 0 0 0 0

0 76.886 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

230.95 0 0 0 0 0 0 0 0 80.01 0 0 0 0 0 0 78.141 0 0 0 0 0 0 154.69 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 157.07 0 0 161.07 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 79.124 0 78.141 0 0 76.92 0 0 0 0 0 0 0 0 0 0 0 0 0 78.001 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 128.28 0 0 0 62.948 0 0 0 0 0 0 0 0 154.95 0 0 0 80.368 0 0 0

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库Floyd最短路径算法(2)在线全文阅读。