Shortest_path_finding_Dijkstra's Algorithm

1 collaborator

Jie Zhu (Author)

WHAT IS IT?

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks.

HOW IT WORKS

(what rules the agents use to create the overall behavior of the model)

HOW TO USE IT

Step.1 - select the types of network; Step.2 - click "setup" to initialize the network; Step.3 - click to run the algorithm; Step.4 - print out the optimal routes from A to B

THINGS TO NOTICE

(suggested things for the user to notice while running the model)

THINGS TO TRY

(suggested things for the user to try to do (move sliders, switches, etc.) with the model)

EXTENDING THE MODEL

(suggested things to add or change in the Code tab to make the model more complicated, detailed, accurate, etc.)

NETLOGO FEATURES

(interesting or unusual features of NetLogo that the model uses, particularly in the Code tab; or where workarounds were needed for missing features)

RELATED MODELS

(models in the NetLogo Models Library and elsewhere which are of related interest)

CREDITS AND REFERENCES

writeen by Jie Zhu Contact: jess.zhu@hotmail.com

Comments and Questions

Please start the discussion about this model! (You'll first need to log in.)

Click to Run Model

globals [

  Q
  S
]

breed [vs v]



vs-own [

  temp-dist
  optimal-routes
  prev

]


links-own [
  dist
]

to setup
  ca

  if Network_Options = "1_simple network"[
  create-vs 7 [
    set shape "circle"
    set size 1
    set color gray
  ]

  set q []
  set s []
  let num ["A" "B" "C" "E" "D"  "G" "F"]
  let x [-5 -5 0 5 5 10 7.5]
  let y [-5  5 0 -5 5 0 10]
  foreach sort vs [ a ->
    ask a [
      set label first num
      set num butfirst num
      set xcor first x
      set ycor first y
      set x butfirst x
      set y butfirst y
      set q lput self q
      set temp-dist 1000000
      set optimal-routes []
      set prev nobody
    ]
  ]
  ask v 0 [set temp-dist 0]

  ask vs [
    create-links-with other vs with [distance myself <= 10]
  ]
  ask v 6 [create-link-with v 5 [set dist 3 set label 3]]
  ask link 2 5 [die]
  ask link 0 1 [set dist 4 set label 4]
  ask link 0 2 [set dist 3 set label 3]
  ask link 0 3 [set dist 7 set label 7]
  ask link 1 2 [set dist 6 set label 6]
  ask link 1 4 [set dist 5 set label 5]
  ask link 2 4 [set dist 11 set label 11]
  ask link 2 3 [set dist 8 set label 8]
  ask link 4 3 [set dist 2 set label 2]
  ask link 4 6 [set dist 2 set label 2]
  ask link 4 5 [set dist 10 set label 10]
  ask link 3 5 [set dist 5 set label 5]
  ]


  if Network_Options = "2_random network" [
    create-vs 100 [
    set shape "circle"
    set size 0.2
    set color gray
    setxy random-xcor random-ycor
  ]
    set q []
    set s []
    foreach sort vs [ a ->
    ask a [
      set q lput self q
      set temp-dist 1000000
      set optimal-routes []
      set prev nobody
    ]
  ]

  ask vs [
    create-links-with other vs with [distance myself <= 10]
  ]
  ask links [set dist link-length]

  ask v 0 [set temp-dist 0 set size 0.5 set color yellow]

  ]
end 

to cal

  let now v 0
  ask now [set color red]
  while [length Q > 0] [
    ask now [
      set q remove self q
      let now-dist temp-dist
      foreach sort link-neighbors with [color != red] [ a ->
        ask a [
          let w 0
          ask link-with now [set w dist]
          if (now-dist + w) < temp-dist [
            set temp-dist now-dist + w
            set prev now
          ]
        ]
      ]
    ask min-one-of vs with [color != red] [temp-dist][
      set color red
      set q remove self q
      ask link-with prev [set color red]
      set optimal-routes [optimal-routes] of prev
      set optimal-routes lput prev optimal-routes
;      set optimal-routes lput self optimal-routes
      set now self
    ]
  ]
 ]

  ask vs [set optimal-routes lput self optimal-routes]
  ask v 0 [set temp-dist 0 set size 0.5 set color yellow]
end

There is only one version of this model, created over 7 years ago by Jie Zhu.

Attached files

File	Type	Description	Last updated
Shortest_path_finding_Dijkstra's Algorithm.png	preview	Preview for 'Shortest_path_finding_Dijkstra's Algorithm'	over 7 years ago, by Jie Zhu	Download

This model does not have any ancestors.

This model does not have any descendants.

NetLogo