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 #

1. BFS(Breadth-First-Search),
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<Integer> used = new HashSet<Integer>();

 // not visited node
 HashSet<Integer> notUsed = new HashSet<Integer>();
 
 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<graph.length; v++){
   if(graph[u][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<Integer> uI = used.iterator();
  while(uI.hasNext()){
   int used = uI.next();
   
   Iterator<Integer> 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<graph.length; i++){
   for(int j=0; j< graph.length; j++){
    
    String pr = "";
    int val = graph[i][j];
    if(val < 10){
     pr = "0"+ val; 
    }else{
     pr = val +"";
    }
    System.out.print(pr + " ");
   }
   System.out.println();
  }
 }
 
 public void firstCaseInit(){
  int count = 9;
  
  graph = new int [count][count];
  dijsktraGraph = new int [count][count];
  dist = new int[count];
  previous = new int[count];
  startPosition = 0;
   
   used= new HashSet<Integer>();
   notUsed= new HashSet<Integer>();
  
  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<count; i++){
   notUsed.add(i); 
  }
 }
 
 public void secondCaseInit(){
  int count = 7;
  
  graph = new int [count][count];
  dijsktraGraph = new int [count][count];
  dist = new int[count];
  previous = new int[count];
  
  startPosition = 1;
  
  used= new HashSet<Integer>();
  notUsed= new HashSet<Integer>();
  
  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<count; i++){
   notUsed.add(i); 
  }
 }
 
 private void printPath(int i) {
  if(i != startPosition){
   System.out.print(i + "to " + previous[i] + ", ");
   printPath(previous[i]);
  }else{
   System.out.println(i + " is last ");
  }
 }
}

Comments

Popular posts from this blog

Project euler 169 found clue

Floyd-Warshall's algorithm