Microcity是大连海事大学交通运输工程学院的孙卓教授自主开发的一款集3D仿真、空间数据分析等众多功能于一体的软件。本文使用lua语言，利用Microcity软件进行编译，分别使用Dijkstra与Floyd两种算法对拓扑化后的航线网络图求解最短路径。
拓扑化后的航线网络图：
部分路段ID、起点ID、终点ID、实际路长数据：
?
一、Dijkstra算法计算从起点到各点的最短路代码
Links=GetControl("links.shp")
Nodes=GetControl("nodes.shp")
marked={}
stpdis={}
preid={}
startid=1 --本例设置起点为1
a={}
for inodes0 = 1, GetRecCount(Nodes) do --数组初始化
id0 = GetValue(Nodes,"ID",inodes0)
marked[id0] = false --标记数组
stpdis[id0] = 100000000 --最短距离
preid[id0] = -1 --前溯节点号
end
crtid = startid --设置当前节点为起点
marked[crtid] = true
stpdis[crtid] = 0
judge = false --设置判断变量
while not judge do --判断变量（存在未永久标号的点）
for ilinks = 1, GetRecCount(Links) do --搜索所有路段
linko = GetValue(Links, "O", ilinks) --得到路段起点
linkd = GetValue(Links, "D", ilinks) --得到路段终点
linkdis = GetValue(Links, "W", ilinks)
if linko == crtid then --如果与当前节点邻接
tmpid = linkd
if stpdis[crtid] + linkdis < stpdis[tmpid] then --并且另一端点的最短距离较大
stpdis[tmpid] = stpdis[crtid] + linkdis
preid[tmpid] = crtid --修改另一端点的最短距离和前溯节点
end
elseif linkd == crtid then
tmpid = linko
if stpdis[crtid] + linkdis < stpdis[tmpid] then --并且另一端点的最短距离较大
stpdis[tmpid] = stpdis[crtid] + linkdis
preid[tmpid] = crtid --修改另一端点的最短距离和前溯节点
end
end
end
for inodes1 = 1, GetRecCount(Nodes) do
id1 = GetValue(Nodes,"ID",inodes1)
judge = true
if not marked[id1] then --若不存在未永久标号的点，判断变量变为true,此时所有点都已得到永久标号，跳出本循环，不进入下一个if语句并跳出while大循环
judge = false --若存在未永久标号的点，判断变量仍为false
crtid = id1 --设置下一个当前节点暂时为该未永久标号的点
break
end
end
if not judge then
for inodes2 = 1, GetRecCount(Nodes) do --搜索所有节点
id2 = GetValue(Nodes,"ID",inodes2)
if not marked[id2] and stpdis[id2] < stpdis[crtid] then --找到未标记的有最小距离的节点
crtid = id2 --重新设置当前节点
end
end
marked[crtid] = true --标记新的当前节点
end
end
for inodes3 = 1, GetRecCount(Nodes) do
id3 = GetValue(Nodes,"ID",inodes3)
Print("destination point",id3,":",stpdis[id3]) --输出当前点及到其最短距离
n = 1
id = id3
while id ~= startid do --倒序存储
a[n] = preid[id]
id = preid[id]
n = n+1
end
while n ~= 1 do --正序输出
Print(a[n-1])
n = n-1
end
Print(id3)
end二、Floyd算法计算从各点到各点的最短路代码
Links = GetControl("links.shp")
Nodes = GetControl("nodes.shp")
N = GetRecCount(Nodes)
L = GetRecCount(Links)
--初始化距离矩阵dis和前置跳转点矩阵path
--由于航线图左右侧同一点连通，需设置两个判断变量处理矩阵
judge1 = {}
judge2 = {}
for i = 1, N do
id = GetValue(Nodes, "ID", i)
judge1[id] = true --大循环的判断变量1初始化
end
num = 0
dis = {}
path = {}
for i1 = 1, N do
id1 = GetValue(Nodes, "ID", i1)
--每次大循环都需将小循环的判断变量2重新初始化
for i0 = 1, N do
id0 = GetValue(Nodes, "ID", i0)
judge2[id0] = true
end
--若大循环的判断变量1为true（即未检索过该id）才会继续处理
if judge1[id1] then
dis[id1] = {}
path[id1] = {}
for i2 = 1, N do
id2 = GetValue(Nodes, "ID", i2)
--若小循环的判断变量2为true（即未检索过该id）才会继续处理
if judge2[id2] then
if id1 == id2 then --各点到自己的矩阵处理
dis[id1][id2] = 0
path[id1][id2] = id2
else --各点到其它点的矩阵处理
dis[id1][id2] = 1000000 --初始设为无穷大
path[id1][id2] = id2
end
judge2[id2] = false --若小循环已检索该点，更新判断变量2
end
end
judge1[id1] = false --若大循环已检索该点，更新判断变量1
num = num + 1 --求得最终共有几个不重复id的点（即矩阵的行数或列数）
end
end
--输入航线图的路段距离
for linki = 1, L do
o = GetValue(Links, "O", linki) --得到路段起点
d = GetValue(Links, "D", linki) --得到路段终点
w = GetValue(Links, "W", linki) --得到路段距离
dis[o][d] = w --无向图处理
dis[d][o] = w --无向图处理
end
--Floyd算法核心步骤
for k = 1, num do --中间点循环
for v = 1, num do --起点循环
for w = 1, num do --终点循环
if dis[v][w] > (dis[v][k] + dis[k][w]) then
dis[v][w] = dis[v][k] + dis[k][w]--更新距离矩阵dis
path[v][w] = path[v][k] --更新前置跳转点矩阵path
end
end
end
end
--输出最短距离
for i = 1, num do
for j = 1, num do
Print(i,"到",j,"的最短路长为：",dis[i][j])
end
end
--输出最短距离经过路径（以1为起点将结果与迪杰斯特拉算法结果对比）
v = 1
for i = 1, num do
w = i
k = path[v][w]
Print(v,"到",w,"的最短路径为：")
Print(v)
while k ~= w do --搜索前置跳转点矩阵直至终点
Print(k)
k = path[k][w]
end
Print(w)
end
结果对比：Dijkstra算法适合求解单源最短路问题，Floyd算法适合求解多源最短路问题。除此之外，计算最短路径的算法还有Bellman-Ford算法、SPFA算法、A*算法等等。
Microcity下载链接：https://microcity.github.io