Разобрался.
Но возникла непонятная проблема.
Если в data вносить дистанцию через переменую, то почему-то путь показывает ACE, хотя ближе ABE.
global d := {"A": [0,0], "B": [1,1], "C": [-2,2], "E": [2,3]}
AB := round(points_dist("A","B"), 2)
AC := round(points_dist("A","C"), 2)
BE := round(points_dist("B","E"), 2)
CE := round(points_dist("C","E"), 2)
msgbox, AB: %AB%`nAC: %AC%`nBE: %BE%`nCE: %CE%
data =
(
A B '%AB%'
A C '%AC%'
B E '%BE%'
C E '%CE%'
)
nodes:=[], Distance := []
for each, line in StrSplit(data, "`n" , "`r")
{
field := StrSplit(line,"`t"), nodes[field.1] := 1, nodes[field.2] := 1
, Distance[field.1,field.2] := field.3 , Distance[field.2,field.1] := field.3
}
for node, v in nodes
nodeList .= (nodeList?"|":"") node (A_Index=1?"|":"")
Gosub, Routing
Gosub, result
return
Routing:
arr := []
From := "A"
To := "E"
arr.Push(To)
res := Dijkstra(data, From)
Loop % objCount(nodes)
{
for xTo , xFrom in res.2
{
if (xTo = To)
{
arr.insertAt(1, xFrom)
To := xFrom
if (xFrom = From)
return
}
}
}
return
result:
for k, v in arr
{
msgbox % v
}
return
Dijkstra(data, start){
nodes := [], dist := [], Distance := [], dist := [], prev := [], Q := [], min := "x"
for each, line in StrSplit(data, "`n" , "`r")
{
field := StrSplit(line,"`t"), nodes[field.1] := 1, nodes[field.2] := 1
, Distance[field.1,field.2] := field.3, Distance[field.2,field.1] := field.3
}
dist[start] := 0, prev[start] := ""
for node in nodes {
if (node <> start)
dist[node] := "x"
, prev[node] := ""
Q[node] := 1
}
while % ObjCount(Q) {
u := MinDist(Q, dist).2
for node, val in Q
if (node = u) {
q.Remove(node)
break
}
for v, length in Distance[u] {
alt := dist[u] + length
if (alt < dist[v])
dist[v] := alt
, prev[v] := u
}
}
return [dist, prev]
}
;-----------------------------------------------
MinDist(Q, dist){
for node , val in Q
if A_Index=1
min := dist[node], minNode := node
else
min := min < dist[node] ? min : dist[node] , minNode := min < dist[node] ? minNode : node
return [min,minNode]
}
ObjCount(Obj){
for key, val in Obj
count := A_Index
return count
}
getDist(pos1,pos2) {
if(!pos1 || !pos2)
return 0
return Sqrt((pos1[1]-pos2[1])*(pos1[1]-pos2[1])+(pos1[2]-pos2[2])*(pos1[2]-pos2[2]))
}
points_dist(p1, p2)
{
return getDist([d[p1][1],d[p1][2]],[d[p2][1],d[p2][2]])
}
Если дистанцию записать в ручную так, то нормально выводить результат ABE
data =
(
A B 1.41
A C 2.83
B E 2.24
C E 4.12
)
nodes:=[], Distance := []
for each, line in StrSplit(data, "`n" , "`r")
{
field := StrSplit(line,"`t"), nodes[field.1] := 1, nodes[field.2] := 1
, Distance[field.1,field.2] := field.3 , Distance[field.2,field.1] := field.3
}
for node, v in nodes
nodeList .= (nodeList?"|":"") node (A_Index=1?"|":"")
Gosub, Routing
Gosub, result
return
Routing:
arr := []
From := "A"
To := "E"
arr.Push(To)
res := Dijkstra(data, From)
Loop % objCount(nodes)
{
for xTo , xFrom in res.2
{
if (xTo = To)
{
arr.insertAt(1, xFrom)
To := xFrom
if (xFrom = From)
return
}
}
}
return
result:
for k, v in arr
{
msgbox % v
}
return
Dijkstra(data, start){
nodes := [], dist := [], Distance := [], dist := [], prev := [], Q := [], min := "x"
for each, line in StrSplit(data, "`n" , "`r")
{
field := StrSplit(line,"`t"), nodes[field.1] := 1, nodes[field.2] := 1
, Distance[field.1,field.2] := field.3, Distance[field.2,field.1] := field.3
}
dist[start] := 0, prev[start] := ""
for node in nodes {
if (node <> start)
dist[node] := "x"
, prev[node] := ""
Q[node] := 1
}
while % ObjCount(Q) {
u := MinDist(Q, dist).2
for node, val in Q
if (node = u) {
q.Remove(node)
break
}
for v, length in Distance[u] {
alt := dist[u] + length
if (alt < dist[v])
dist[v] := alt
, prev[v] := u
}
}
return [dist, prev]
}
;-----------------------------------------------
MinDist(Q, dist){
for node , val in Q
if A_Index=1
min := dist[node], minNode := node
else
min := min < dist[node] ? min : dist[node] , minNode := min < dist[node] ? minNode : node
return [min,minNode]
}
ObjCount(Obj){
for key, val in Obj
count := A_Index
return count
}
getDist(pos1,pos2) {
if(!pos1 || !pos2)
return 0
return Sqrt((pos1[1]-pos2[1])*(pos1[1]-pos2[1])+(pos1[2]-pos2[2])*(pos1[2]-pos2[2]))
}
points_dist(p1, p2)
{
return getDist([d[p1][1],d[p1][2]],[d[p2][1],d[p2][2]])
}
Помогите пожалуйста.