## Friday, August 29, 2014

### Dijkstra's Algorithm Implementation in Java

This program implements Dijkstra's algorithm for finding the shortest path to all vertices from the given source in a graph. The code is simple enough. I've added comments wherever necessary.

Graph used in this example:

Code:

```import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Node {

boolean showMoreInfo = true;
int distanceFromSource = 0;
String name;
public Map<Node, Integer> neighbors = new HashMap<>();

Node(String name) {
this.name = name;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("Node: ").append(name).append("\n");

sb.append("Distance from source: ").append(distanceFromSource).append("\n");

if (showMoreInfo) {
sb.append("Neighbor nodes: \n");
for (Node node : neighbors.keySet()) {
sb.append(node.name).append("  Distance: ").append(this.neighbors.get(node)).append("\n");
}

sb.append("\n");
}
return sb.toString();
}
}

public class DijkstrasAlgorithm {
List<Node> nodes = new ArrayList<>();

public void drawGraph() {
Node s = new Node("s");

//Two immediate (reachable) neighbors of Node s
Node t = new Node("t");
Node y = new Node("y");
s.neighbors.put(t, 10);
s.neighbors.put(y, 5);

//One of the two immediate (reachable) neighbors of Node t
Node x = new Node("x");
t.neighbors.put(x, 1);
t.neighbors.put(y, 2);

y.neighbors.put(t, 3);
y.neighbors.put(x, 9);

//Last Node z (immediately reachable from x and y nodes)
Node z = new Node("z");
x.neighbors.put(z, 4);
y.neighbors.put(z, 2);
z.neighbors.put(x, 6);
z.neighbors.put(s, 7);

//Now add these to List<Node> nodes
}

private void initializeNodes(){
for(Node node:nodes)
node.distanceFromSource = Integer.MAX_VALUE;
nodes.get(0).distanceFromSource = 0;
}

private void relax(Node previous, Node next){
if(next.distanceFromSource>previous.distanceFromSource+previous.neighbors.get(next)){
next.distanceFromSource = previous.distanceFromSource+previous.neighbors.get(next);
}
}

private Node getMin(List<Node> nodes){
int min = Integer.MAX_VALUE;
int minIndex = -1;
for(int i=0;i<nodes.size();++i){
if(nodes.get(i).distanceFromSource<min){
min = nodes.get(i).distanceFromSource;
minIndex = i;
}
}
return nodes.get(minIndex);
}

public void dijkstra(){
List<Node> nodesCopy = new ArrayList<>();

while(!nodesCopy.isEmpty()){
Node min = getMin(nodesCopy);

Map<Node, Integer> neighbors = min.neighbors;
for(Map.Entry<Node, Integer> me:neighbors.entrySet()){
relax(min, me.getKey());
}
nodesCopy.remove(min);
}
}

public static void main(String[] args){
DijkstrasAlgorithm da = new DijkstrasAlgorithm();
da.drawGraph();
da.initializeNodes();
da.dijkstra();

System.out.println(da.nodes.size());
for(Node node:da.nodes)
System.out.println(node);
}
}```

Output:

Node: s
Distance from source: 0
Neighbor nodes:
t  Distance: 10
y  Distance: 5

Node: t
Distance from source: 8
Neighbor nodes:
x  Distance: 1
y  Distance: 2

Node: y
Distance from source: 5
Neighbor nodes:
x  Distance: 9
t  Distance: 3
z  Distance: 2

Node: x
Distance from source: 9
Neighbor nodes:
z  Distance: 4

Node: z
Distance from source: 7
Neighbor nodes:
x  Distance: 6
s  Distance: 7