Netlogo Dijkstra 算法

Question

to-report find-path [ init final ]
  ask init [set dist_d 0]
  let current init
  let p_dij []
  set p_dij insert-item 0 p_dij current 
  show "dij"
  while [not (current = final)] 
  [
    ask [neighbors with [pcolor = yellow and not (dist_d = -1)]] of current [set dist_d min (list dist_d (1 + [dist_d] of current))]
    ask current [set dist_d -1]
    let min_d min [dist_d] of neighbors
    set current one-of neighbors with [dist_d = min_d and pcolor = yellow]
    set p_dij insert-item (length p_dij - 1) p_dij current 
  ]
  ask patches with [pcolor = yellow] [set plabel dist_d set plabel-color red]
  report p_dij
end

我正在尝试使用 Dijkstra 算法找到最短路径。邻居有问题，每次程序试图找到下一个当前节点，它都会回到init。

Answer 1

这不是您问题的直接答案，如果您正在尝试弄清楚如何编写 Dijkstra 算法作为您自己的练习，那么这对您没有帮助，但如果您只是在寻找最短的路径，您始终可以使用网络扩展中的 nw:path-to。

该原语实际上在幕后使用了 Dijkstra 算法。

然而，为了使用它，您需要一个实际的网络，因此您必须使用海龟而不是补丁。然而，这很容易做到。假设你有一个名为 nodes 的海龟品种，你可以在每个补丁上放置一个节点：

ask patches [
  sprout-nodes 1 [
    set color pcolor ; give the node the same color as the patch
    set hidden? true ; hide the node if you prefer not seeing it
  ]
]

然后您可以在黄色节点之间创建链接：

ask nodes with [ color = yellow ] [
  create-links-with (nodes-on neighbors) with [ color = yellow ]
]

从一个黄色节点到另一个黄色节点的路径就是：

let yellow-nodes nodes with [ color = yellow ]
show [ nw:path-to one-of other yellow-nodes ] of one-of yellow-nodes

如果你只想要距离，可以使用nw-distance-to。

Netlogo Dijkstra 算法

Netlogo Dijkstra algorithm

dijkstra

netlogo