給定圖上的最佳路徑

Question

我正在netLogo中的一個項目中工作，在該項目中，我有一個隨機的網絡，其中每個鏈接都分配了一個帶寬。該算法自己選擇一個隨機的源和目標，之後必須選擇這兩者之間的最佳路徑。

我的問題是如何通過探索所有可能的路徑來選擇最佳路徑。

茲附上我的模型的源代碼：

breed[nodes node] 
    breed[ants ant ] 

    globals [nodename nodenumbersource nodenumberdestination relaynode dead-network num  ] 
    nodes-own[visited ] 
    links-own[visit bandwidth] 



    ants-own 
    [ 
    distance-gone 
    distance-to-go 
    target-node 
    current-node 
    ] 




    to cr11 
    ask nodes with [label = "Source"] 
    [ 
    set num count (link-neighbors) 
    ] 
    create-ants num ;num-ants 
    [ 

    let n one-of nodes with [label = "Source"] 

    setxy ([xcor] of n) ([ycor]of n) 
    set current-node n 
    set color white set size 0.95 
    set distance-gone 0 
    set distance-to-go 0 
    set target-node one-of nodes with [ label = "Relay Node" ] ;nobody 
    ] 
    end 

    to face-targets 
    ask ants ;with [ target-node]; = node 4 ] ;nobody ] 
    [ 

    let d 0 

    face (one-of nodes with [ label = "Relay Node" ]);target-node 
     ask current-node [ 
     set d distance (one-of nodes with [ label = "Relay Node" ]);target-node) 

     ] 
     set distance-to-go d 

     ] 
     end 

     to move-forward 
     face-targets 

     ask ants [ 
     while [ distance-gone < (distance-to-go )] 
     [ 


     fd 1 
     set distance-gone (distance-gone + 1) 
     ] 
     ] 
     ask ants [ 
      if distance-gone < distance-to-go 

      [ 
      set current-node target-node 
      setxy ([xcor] of current-node) ([ycor] of current-node) 
      set distance-gone 0 
      set distance-to-go 0 

      ] 
      ] 
      end 





       ;This is used to design the Network 
       to setup 
       setup1 
       setup-spatially-clustered-network 
       ask links [set color white 
       set visit false 
       set bandwidth (5 + random 10) ;min bw 5 max 15 
       ] 


       end 



      to setup1 

      __clear-all-and-reset-ticks 
      set dead-network 0 
      create-nodes number-of-nodes 
       [ 

       setxy (random-xcor * 0.95) (random-ycor * 0.95) 
       set shape "circle" 
       set color green 
       set visited false 
       set label who 
       ] 


      end 

      ;Links are created for the nodes 
      to setup-spatially-clustered-network 
      let num-links (6 * number-of-nodes)/2 

      while [count links < num-links ] 
      [ 
       ask one-of turtles 
       [ 
       let choice (min-one-of (other turtles with [not link-neighbor? myself]) 
       [distance myself]) 
      if choice != nobody [ create-link-with choice 

     ] 
     ] 
     ] 

     repeat 10 
     [ 
     layout-spring turtles links 0.3 (world-width/(sqrt number-of-nodes)) 1 
     ] 
     end 

     ;This is to Generate Message for nodes 
     to test1 
     ask one-of nodes 
     [ 
     set color red 
     set label "Source" 
     set nodenumbersource who 


     ] 
      ask one-of nodes with [color = green] 
     [ 
      set color red 
      set label "Destination" 
      set nodenumberdestination who 


      ] 

     cr11 


     end 



     to test3 




     ask turtles with [label = "Source"] 
     [ 
     set label "ants moving" 

     ask my-links 
     [ 
     set color green 
     ] 


      ask link-neighbors 
     [ 
      set color blue 

     ] 




      ask min-one-of turtles with [color = blue and my-links] [distance turtle nodenumberdestination ] 
      [ 
      ask max-one-of my-links [bandwidth ] 
      [ 


      set color red 
      ] 
      set color white 
      set relaynode who 
      set label "Relay Node" 
      ] 



      ; face-targets 
      move-forward 
      end 

    to test4 


     ask turtle nodenumberdestination 
     [ 
     while [color != white] 
     [ 


     ask turtle relaynode 
     [ 
     set label "" 

     ask my-links 
     [ 
      set color green 
      ] 
     ask link-neighbors 
     [ 


     set color yellow 
     ] 
     ] 

     ask turtles with [color = yellow] 

     [ 
     set color violet 
     ] 

     ask turtles with [color = violet] with [visited = false] 
     [ 
     set color magenta 
     ] 
     ask min-one-of turtles with [color = magenta] [distance turtle nodenumberdestination] 
     [ 
      set color white 
     set relaynode who 
     set label "Relay Node" 
     set visited true 
     ] 
     move-forward 

      ] 
     ] 








     end 

     to test6 
     ask nodes ; turtles 
     [ 
     set color green 
     set visited false 
     set label "" 
     ] 
     ask links 
     [ 
     set color white 
     set visit false 
     ] 
     end 


     to test5 

     test1 
     test3 
     test4 


    end 

Answer 1

可以使用NW-Extension爲！只需download it並將其粘貼在NetLogo的擴展文件夾中。然後，在你的模型，你可以通過添加

extensions [ nw ]

你的代碼的頂部開始使用。然後，您可以使用其中一個weighted-path-to基元來獲取沿兩個節點之間最短路徑的海龜或鏈接。

請注意，nw擴展正處於積極的發展階段，儘管它已經過很好的測試。您還必須使用最新版本的NetLogo。

如果你想自己實現它，Dijkstra's algorithm是經典的解決方案，如果你有你的圖中非負權重。