Shortest path algorithm

Shortest path algorithm preview image

1 collaborator

Gil Alvaro Gil (Author)

Tags

(This model has yet to be categorized with any tags)
Visible to everyone | Changeable by the author
Model was written in NetLogo 5.0 • Viewed 943 times • Downloaded 82 times • Run 0 times
Download the 'Shortest path 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.)


## COPYRIGHT AND LICENSE

Copyright 2012 Alvaro Gil alvaro.gil@polymtl.ca

![CC BY-NC-SA 3.0](http://i.creativecommons.org/l/by-nc-sa/3.0/88x31.png)

## HOW TO CITE

If you mention this model in an academic publication, I ask that you include this citation for the model

- Gil, Alvaro (2012), Application of Kruskal's and Dijkstra's Algorithms with NetLogo. École Polytechnique de Montréal, QC. (alvaro.gil@polymtl.ca)

Comments and Questions

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

Click to Run Model

turtles-own [voisins]
globals [arr_e]
extensions [table]

to setup
  ca
  crt Nodes
  set-default-shape turtles "circle"
  ask turtles [setxy random-xcor random-ycor 
    if Show_Names? = True [show-names]]
  ;ask patches [set pcolor white]
end 

to create-complete-graph
  ask links [die]
  ask turtles [create-links-with other turtles]
end 

to create-random-graph
  ask links [die]
  ask turtles [create-links-with n-of ((random Max_Connections) + 1) other turtles]
end 

to show-names
   ifelse label = ""
   [set label (word who " ")] 
    [set label ""]
end 

to kruskal
  set arr_e []
  ask links [set hidden? true]
  let l [] 
  foreach [self] of links [
    set l lput ([link-length] of ?) l] 
  set l sort l
  ;first pair
  ask first([self] of links with [link-length = first(l)])
  [set color 25
    set hidden? false
    set thickness 0.3 
    let e1 [who] of end1
    let e2 [who] of end2
    let tempar []
    set tempar lput e1 tempar
    set tempar lput e2 tempar
    set arr_e lput tempar arr_e]
  set l remove-item 0 l
  while [length(l) > 0] [
   let li first([self] of links with [link-length = first(l)])
   let e1 [who] of [end1] of li
   let e2 [who] of [end2] of li
   let i 0
   let flag 0
   let p1 -1
   let p2 -1
   while [i < length(arr_e)] [
     if (member? e1 item i arr_e)
      [set p1 i]
      if (member? e2 item i arr_e)
      [set p2 i]
      set i i + 1]
   let case 0
   while [flag = 0] [
     let tempar []
     if p1 != -1 and p1 = p2 [ ;Case1: Both belong to the same array
       set case 1
       set flag 2]
     if p1 = -1 and p1 = p2 [  ;Case2: Nobody belongs 
      set tempar lput e1 tempar
      set tempar lput e2 tempar
      set arr_e lput tempar arr_e
      set case 2
      set flag 1]
     if p1 != -1 and p2 = -1 [ ;Case 3: Only e1 exists in one group
       set tempar item p1 arr_e
       set arr_e remove tempar arr_e
       set tempar lput e2 tempar
       set arr_e lput tempar arr_e
       set case 3
       set flag 1]
     if p1 = -1 and p2 != -1 [ ;Case 4: Only e2 exists in one group
       set tempar item p2 arr_e
       set arr_e remove tempar arr_e
       set tempar lput e1 tempar
       set arr_e lput tempar arr_e
       set case 4
       set flag 1]
     if p1 != -1 and p2 != -1 and flag = 0 [ ;Case 5: Both already belong to different groups
       let g1 item p1 arr_e
       let g2 item p2 arr_e
       set tempar sentence g1 g2
       set arr_e remove g1 arr_e
       set arr_e remove g2 arr_e
       set arr_e lput tempar arr_e
       set case 5
       set flag 1]
   ]
   if flag = 1
   [ask li [
     set color 25
     set hidden? false
    set thickness 0.3 ]
   ]
   set l remove-item 0 l
   ]
  set arr_e remove-duplicates arr_e
  ask links with [hidden? = true] [die]
end 

to-report dijkstra
  let tempar []
  ask turtle Origin [
    let r []
    let distan []
    let l sort([who] of other turtles)
    let from_array l
    let index table:make 
    let t 0
    while [t < length(l)] [
      set r lput([]) r
      set distan lput 999999 distan
      table:put index (item t l) (position (item t l) l)
      set t t + 1]
    ;First turn
    let next_index []
    let j 0
    while [j < length(l)] [
      let de item j l
      if is-link? link who de
        [let dd 0
          set next_index lput(de) next_index
          ask link who de [set dd link-length]
          let temproute item j r
          set temproute lput de temproute
          set r replace-item j r temproute
          set distan replace-item j distan dd]
      set j j + 1]
    while [length(from_array) > 0] [
      ;print "ENTER"
      foreach next_index [
        let temp_from ?
        let posic_orig table:get index temp_from
        let k 0
        while [k < length(from_array)] [
          let temp_dest item k from_array
          if temp_dest != temp_from [
            if is-link? link temp_dest temp_from [
              let dd 0
              ask link temp_dest temp_from [set dd link-length]
              let posic_dest table:get index temp_dest
              if item posic_dest distan > (dd + item posic_orig distan) [
                set distan replace-item posic_dest distan (dd + item posic_orig distan)
                let temp_route (item posic_orig r)
                set temp_route lput(temp_dest) temp_route
                set r replace-item posic_dest r temp_route]
            ]]
          set k k + 1]
        set from_array remove temp_from from_array]
      set next_index []
      let i 0
      while [i < length(r)]
        [ if item i r != [] and member? (item i l) from_array [set next_index lput(item i l) next_index]
          set i i + 1]]
    let final_route item (table:get index Destin) r
    set final_route fput(Origin) final_route
    let total_distance item (table:get index Destin) distan
    set tempar lput final_route tempar
    set tempar lput total_distance tempar]
  report tempar
end 

to create-shortest-path
  ask turtles [set color 85]
  ifelse Reset_Network [ask links [die]
    create-random-graph]
  [ask links [
      set color gray
      set thickness 0]]
  if Origin = Destin [user-message "Please select two different nodes" stop]
  ask turtle Origin [set color Red]
  ask turtle Destin [set color Red]
  let tempar dijkstra
  let final_route item 0 dijkstra
  let total_distance item 1 dijkstra
  print (word "The shortest path between Origin and Destination nodes is " final_route " for " total_distance)
  let i 0
  while [i < length(final_route) - 1] [
    if (item (i + 1) final_route) != Destin [ask turtle (item (i + 1) final_route) [set color 27]]
    ask link (item i final_route) (item (i + 1) final_route) [
      set color red
      set thickness 0.3] 
    set i i + 1]
end 

There is only one version of this model, created over 3 years ago by Alvaro Gil.

Attached files

File Type Description Last updated
Shortest path algorithm.png preview Preview for 'Shortest path algorithm' over 3 years ago, by Alvaro Gil Download

This model does not have any ancestors.

This model does not have any descendants.