【理论知识的，可以参考】

漫画：图的最短路径问题

最短路径算法

 

该算法得到的是单源最短路径，即起点到任意目标点的距离

【lua实现】

 1 local Dijkstra = {}
 2 Dijkstra.__index = Dijkstra
 3 
 4 function Dijkstra.new(g)
 5     local obj = {}
 6     setmetatable(obj, Dijkstra)
 7 
 8     obj:ctor(g)
 9     return obj
10 end
11 
12 function Dijkstra:ctor(g)
13     self.graph = g
14     self.startVertex = nil
15     self.visitFrom = {} --点之间的遍历关系, key:当前遍历点, value:上一个遍历点
16     self.distFromStart = {} --从起始点到该点的距离
17 end
18 
19 function Dijkstra:IsReachable(endVertex)
20     return self.distFromStart[endVertex].dist < 9999
21 end
22 
23 function Dijkstra:VisitAllReachable(startVertex)
24     self.startVertex = startVertex
25     self.visitFrom = {}
26     self.distFromStart = {}
27 
28     for i=1,self.graph:GetVertexCount() do
29         local v = self.graph:GetVertex(i)
30         self.distFromStart[v] = {
31             dist = 9999,
32             used = false,
33         }
34     end
35 
36     local distInfo = self.distFromStart[startVertex]
37     distInfo.dist = 0
38     distInfo.used = true
39 
40     local v = startVertex
41     while true do
42         local adjList = self.graph:GetAdjacent(v)
43         for i=1,#adjList do
44             local adjVInfo = adjList[i]
45             local oldDist = self.distFromStart[adjVInfo.v].dist
46             local newDist = self.distFromStart[v].dist + adjVInfo.w
47             if newDist < oldDist then
48                 self.distFromStart[adjVInfo.v].dist = newDist
49                 self.visitFrom[adjVInfo.v] = v
50             end
51         end
52 
53         --从距离最小的点继续往后遍历
54         --从ta开始过1次, 后面将不会再从ta开始
55         local minDistInfo = nil
56         local minV = nil
57         for i=1,self.graph:GetVertexCount() do
58             local v = self.graph:GetVertex(i)
59             local distInfo = self.distFromStart[v]
60             if not distInfo.used then
61                 if nil == minDistInfo or distInfo.dist < minDistInfo.dist then
62                     minDistInfo = distInfo
63                     minV = v
64                 end
65             end
66         end
67         if nil == minDistInfo then --所有都遍历过了
68             break
69         end
70 
71         minDistInfo.used = true
72         v = minV
73     end
74 end
75 
76 function Dijkstra:GetDist(endVertex)
77     return self.distFromStart[endVertex].dist
78 end
79 
80 function Dijkstra:GetPath(endVertex)
81     if not self:IsReachable(endVertex) then return nil end
82 
83     local pathQueue = {}
84     local v = endVertex
85     while v ~= self.startVertex do
86         table.insert(pathQueue, 1, v)
87         v = self.visitFrom[v]
88     end
89     table.insert(pathQueue, 1, v)
90     return pathQueue
91 end

 

计算下面这张图的最短路径：

 

 

 

 1 function CreateGraph()
 2     local g = WeightedGraph.new()
 3     g:AddVertex("A")
 4     g:AddVertex("B")
 5     g:AddVertex("C")
 6     g:AddVertex("D")
 7     g:AddVertex("E")
 8     g:AddVertex("F")
 9     g:AddVertex("G")
10 
11     g:AddEdge("A", "B", 5)
12     g:AddEdge("A", "C", 2)
13     g:AddEdge("B", "D", 1)
14     g:AddEdge("B", "E", 6)
15     g:AddEdge("C", "D", 6)
16     g:AddEdge("C", "F", 8)
17     g:AddEdge("D", "E", 1)
18     g:AddEdge("D", "F", 2)
19     g:AddEdge("E", "G", 7)
20     g:AddEdge("F", "G", 3)
21 
22     --tostring(g)
23     return g
24 end
25 
26 function Test1()
27     local g = CreateGraph()
28     local d = Dijkstra.new(g)
29     d:VisitAllReachable("A")
30     assert(d:IsReachable("B"))
31     assert(d:IsReachable("G"))
32 
33     assert(5 == d:GetDist("B"))
34     assert(2 == d:GetDist("C"))
35     assert(6 == d:GetDist("D"))
36     assert(7 == d:GetDist("E"))
37     assert(8 == d:GetDist("F"))
38     assert(11 == d:GetDist("G"))
39 end
40 Test1()