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 1926 times • Downloaded 140 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.)


Info tab cannot be displayed because of an encoding error

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 almost 10 years ago by Alvaro Gil.

Attached files

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

This model does not have any ancestors.

This model does not have any descendants.