Shortest_path_finding_Dijkstra's Algorithm

Shortest_path_finding_Dijkstra's Algorithm preview image

1 collaborator

Default-person Jie Zhu (Author)

Tags

(This model has yet to be categorized with any tags)
Visible to everyone | Changeable by everyone
Model was written in NetLogo 6.0.2 • Viewed 99 times • Downloaded 4 times • Run 0 times
Download the 'Shortest_path_finding_Dijkstra's Algorithm' modelDownload this modelEmbed this model

Do you have questions or comments about this model? Ask them here! (You'll first need to log in.)


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 about 1 year 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' about 1 year ago, by Jie Zhu Download

This model does not have any ancestors.

This model does not have any descendants.