## Thursday, January 15, 2015

### Dijkstra's algorithm in java

Today I want to post Dijkstra Algorithm.

Dijkstra Algorithm is used to find shortest path.
this algorithm is well-known because many applications which programmed by this algorithm we are using in practice.

Usage,
Subway Map, GeoGraphic Infomation System and so on.

Before posting this algorithm, I had to study many things to understand for this one.

# List #

2. DFS(Depth-First-Search),
3. Prim algorithm,
4. Union Find algorithm,
5. Kruskal algorithm,
6. Topology algorithm,

After writing those code in Java, I was able to totally understand Dijkstra Algorithm, usages where to use and how to customizing,

Pseudocode

1  function Dijkstra(Graph, source):
2
3      dist[source] ← 0                       // Distance from source to source
4      prev[source] ← undefined               // Previous node in optimal path initialization
5
6      for each vertex v in Graph:  // Initialization
7          if vsource            // Where v has not yet been removed from Q (unvisited nodes)
8              dist[v] ← infinity             // Unknown distance function from source to v
9              prev[v] ← undefined            // Previous node in optimal path from source
10          end if
11          add v to Q                     // All nodes initially in Q (unvisited nodes)
12      end for
13
14      while Q is not empty:
15          u ← vertex in Q with min dist[u]  // Source node in first case
16          remove u from Q
17
18          for each neighbor v of u:           // where v has not yet been removed from Q.
19              alt ← dist[u] + length(u, v)
20              if alt < dist[v]:               // A shorter path to v has been found
21                  dist[v] ← alt
22                  prev[v] ← u
23              end if
24          end for
25      end while
26
27      return dist[], prev[]
28
29  end function

this is graph start from node 1

check length (weight)

visit node 2 (minimu length from visited to none visited)
and check neighbors length

visit 3

visit 6

this is what shortest path

and I will show you my java code and this has two testcase

firstcase is from wekipedia

secondcase is from geeksforgeeks

if you like....
if you have question...
if you found something is strange...

Comment plz~

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 package mybook; import java.util.Arrays; import java.util.HashSet; import java.util.Iterator; public class DijkstraTest { int[][] graph ; int[][] dijsktraGraph ; int[] dist; int[] previous; int startPosition ; // visited node HashSet used = new HashSet(); // not visited node HashSet notUsed = new HashSet(); public static void main(String[] args){ DijkstraTest prim = new DijkstraTest(); prim.secondCaseInit(); prim.start(); prim.printValue(prim.dijsktraGraph); // first test // find shortest path from start node prim.printPath(1); prim.printPath(2); prim.printPath(3); prim.printPath(4); prim.printPath(5); prim.printPath(6); // second test prim.firstCaseInit(); prim.start(); prim.printValue(prim.dijsktraGraph); prim.printPath(1); prim.printPath(2); prim.printPath(3); prim.printPath(4); prim.printPath(5); prim.printPath(6); prim.printPath(8); } public void start(){ // start vertex(node) should be set in advance. notUsed.remove(startPosition); used.add(startPosition); checkWeight(startPosition); while (! notUsed.isEmpty()) { // find shortest distance from used usedNode to targetNode int [] node = minimumNode(); int targetNode = node[1]; // remove target from Queue notUsed.remove(targetNode); used.add(targetNode); // draw graph dijsktraGraph[node[0]][node[1]]=1; // check new weight to neighbors of target checkWeight(targetNode); } } /** * check the new distances of neighbors of the targetNode if graph[u][v] + dist[u] < dist[v] * * u = from * v = t * * @param u */ public void checkWeight(int u){ for(int v=startPosition+1; v 0){ if((dist[v] ==0) || notUsed.contains(v) && graph[u][v] + dist[u] < dist[v] ){ dist[v] = graph[u][v] + dist[u]; // chase for the shortest way previous[v] = u; } } } System.out.println(Arrays.toString(dist)); } /** * find targetnode which has min weight in from used node to notUsed node * * @return node[from][to] */ private int[] minimumNode() { int minValue = Integer.MAX_VALUE; int[] node = new int[2]; Iterator uI = used.iterator(); while(uI.hasNext()){ int used = uI.next(); Iterator nI = notUsed.iterator(); while(nI.hasNext()){ int notUsed = nI.next(); if(graph[used][notUsed] > 0){ int distance = dist[used] + graph[used][notUsed]; if( distance < minValue){ minValue = distance; node[0]= used; node[1] = notUsed; } } } } return node; } public void setvalue(int [][] graph, int start, int end, int val){ graph[start][end] = val; graph[end][start] = val; } public void printValue(int graph[][]){ for(int i=0; i(); notUsed= new HashSet(); setvalue(graph, 0, 1, 4); setvalue(graph, 0, 7, 8); setvalue(graph, 1, 7, 11); setvalue(graph, 1, 2, 8); setvalue(graph, 2, 8, 2); setvalue(graph, 8, 6, 6); setvalue(graph, 6, 7, 1); setvalue(graph, 7, 8, 7); setvalue(graph, 2, 3, 7); setvalue(graph, 2, 5, 4); setvalue(graph, 5, 6, 2); setvalue(graph, 3, 5, 14); setvalue(graph, 3, 4, 9); setvalue(graph, 4, 5, 10); for(int i=startPosition; i(); notUsed= new HashSet(); setvalue(graph, 1, 3, 9); setvalue(graph, 1, 2, 7); setvalue(graph, 1, 6, 14); setvalue(graph, 2, 3, 10); setvalue(graph, 2, 4, 15); setvalue(graph, 3, 4, 11); setvalue(graph, 3, 6, 2); setvalue(graph, 4, 5, 6); setvalue(graph, 5, 6, 9); for(int i=startPosition; i