I have developed GIS, and the shortest path query procedure, the shortest speed, 30,000 nodes, 35,000 roads are all traversed, only 1 second. I will tell you the shortest path of the shortest path, I hope everyone will be optimized, and use different languages. I am learning Delphi, ready to use Delphi to make a library, this example is used as the ARC / INFO file by the topology. Where A1, B1, C1 are arrays generated by FNODE, and A1 corresponds to the FNODE, B1 corresponds to Length, and the same A2, B2, C2, is an array generated by TNODE. Indexa1 is a number of starting points corresponding to a certain end point, and INDEXB1 corresponds to the number of starting points connected to it, ie its topologies.
Public Function Shortpath (Startno As Integer, Endno As Integer) AS Single
At the beginning, the end point is the parameter.
Dim Result () AS SINGLE
Dim Result1 AS Integer
Definition result point
DIM S1 As Single
DIM min as sales
DIM II, I, J, AA AS INTEGER
DIM YC () AS Boolean
DIM YCD () as boolean
DIM RS1 () AS SINGLE
Dim no () AS Integer
DIM NOPOINT AS INTEGER
Redim Yc (1 to Maxno) as boolean
Redim Ycd (1 to Maxno) as boolean
Redim RS1 (1 to Maxno) AS Single
Redim Result (1 to 2, 1 to maxno) AS SINGLE
The result of the definition, where Result (1, MAXNO) is the result point, Result (2, maxno) as the result length.
For i = 1 to maxno // MaxNo is the largest number of nodes in the network.
Yc (i) = false // Tagging the point that has been checked.
YCD (i) = false // Tagging has been used by results
RS1 (i) = 1e 38 // Assume that the distance from the starting point to any point is infinite
Next i
Ll = startno // Set the start point.
Yc (ll) = true // Tag start point is true. That is, the result point has been used.
J = 0
For aa = 1 to maxno
Search from the end of the start point
For i = 1 to indexa1 (2, ll) // cycle with the starting point connected to the LL point
Result1 = B1 (INDEXA1 (1, LL) - I 1) identifies the point of the end point connected to the LL point
S1 = C1 (INDEXA1 (1, LL) - I 1) Result (2, LL) finds a length and
If Yc (Result1) = True Then Goto 200 If the next one is checked
If Ycd (Result1) = TRUE THEN // If it has been determined as a result point?
IF RS1> = S1 Then // If this point to the length of the starting point is longer than the current route, replacing
RS1 (Result1) = S1
Result (1, result1) = ll // set to the shortest path to this point is LL point (Part of the Essence)
Result (2, result1) = S1 Set to the shortest path length of this
Goto 200
Else
Goto 200
END IF
END IF
If the above conditions do not match, the following statement is performed.
YCD (Result1) = true
RS1 (Result1) = S1
Result (1, Result1) = LL
Result (2, Result1) = S1
Every time you find one, for the following judgment
J = J 1
Redim Preserve No (1 to j) AS Integer
From the new definition array and make the value of the current point
NO (j) = result1
200 Next I
Search again from the end of the start point, it is no longer marked with the above
For i = 1 to indexb2 (2, ll)
Result1 = a2 (INDEXB2 (1, LL) - i 1)
S1 = C2 (INDEXB2 (1, LL) - I 1) Result (2, ll)
IF YC (Result1) = True Then Goto 300
If Ycd (Result1) = True Then
IF RS1 (Result1)> = S1 THEN
RS1 (Result1) = S1
Result (1, Result1) = LL
Result (2, Result1) = S1
Goto 300
Else
Goto 300
END IF
END IF
YCD (Result1) = true
RS1 (Result1) = S1
Result (1, Result1) = LL
Result (2, Result1) = S1
J = J 1
Redim Preserve No (1 to j) AS Integer
NO (j) = result1
300 Next I
Set the minimum infinity, the shortest path point is empty min = 1e 38MINPOINT = NULL (Optimized section) to find some point for i = aa to jif min> RS1 (NO (i)) THENII = iMin = RS1 (NO (i)) MINPOINT = NO (i) end ifXext i If there is no result, the starting point and the end point do not have the passage exit program if min = 1e 38 Then Exit function (focus optimization) to interchange two points, reduce cycles . NO (ii) = no (aa) NO (aa) = minPoint tag has been judged as a result point to YC (MINPOINT) = truell = minPoint determines whether the result point is equal to the end point, if equals the shortest path if minpoint = Endno Then EXIT Fornext AA Returns the shortest path length stpath = result (2, endno) End Function
