Breaking
Greedy

# Find the shortest paths between nodes in a graph using Dijkstras algorithm

Dijkstras algorithm is an algorithm for finding the shortest paths between nodes in a graph. Dijkstra’s Algorithm solves the single-source shortest path problem in weighted graphs. It is similar to Prims algorithm. Dijkstra algorithm can be used for graphs with all positive weight edges only. Dijkstra is not lacks distribute property.

Write a program to implement Dijkstra’s algorithm

## source Code

```package com.dsacode.Algorithm.greedy;

import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

class Vertex implements Comparable < Vertex >
{
public final String name;
public double minDistance = Double.POSITIVE_INFINITY;
public Vertex previous;
public Vertex(String argName) {
name = argName;
}

public String toString() {
return name;
}
public int compareTo(Vertex other){
return Double.compare(minDistance, other.minDistance);
}
}

class EdgeDijkstra
{
public final Vertex target;
public final double weight;
public EdgeDijkstra(Vertex argTarget, double argWeight){
target = argTarget;
weight = argWeight;
}
}

public class Dijkstra
{
public static void computePaths(Vertex source){
source.minDistance = 0.;
PriorityQueue < Vertex > vertexQueue = new PriorityQueue < Vertex >();

while (!vertexQueue.isEmpty()) {

Vertex u = vertexQueue.poll();

Vertex v = e.target;
double weight = e.weight;
double distanceThroughU = u.minDistance + weight;
if (distanceThroughU < v.minDistance) {
vertexQueue.remove(v);
v.minDistance = distanceThroughU ;
v.previous = u;
}
}
}
}

public static List < Vertex > getShortestPathTo(Vertex target){
List < Vertex > path = new ArrayList < Vertex >();
for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
Collections.reverse(path);
return path;
}

public static void main(String[] args){
Vertex v0 = new Vertex("Delhi");
Vertex v1 = new Vertex("Mumbai");
Vertex v2 = new Vertex("chennai");
Vertex v3 = new Vertex("Bangalore");
Vertex v4 = new Vertex("Pune");

v0.adjacencies = new EdgeDijkstra[]{ new EdgeDijkstra(v1, 5),
new EdgeDijkstra(v2, 10),
new EdgeDijkstra(v3, 8) };
v1.adjacencies = new EdgeDijkstra[]{ new EdgeDijkstra(v0, 5),
new EdgeDijkstra(v2, 3),
new EdgeDijkstra(v4, 7) };
v2.adjacencies = new EdgeDijkstra[]{ new EdgeDijkstra(v0, 10),
new EdgeDijkstra(v1, 3) };
v3.adjacencies = new EdgeDijkstra[]{ new EdgeDijkstra(v0, 8),
new EdgeDijkstra(v4, 2) };
v4.adjacencies = new EdgeDijkstra[]{ new EdgeDijkstra(v1, 7),
new EdgeDijkstra(v3, 2) };
Vertex[] vertices = { v0, v1, v2, v3, v4 };
computePaths(v0);
for (Vertex v : vertices)  {
System.out.println("Distance to " + v + ": " + v.minDistance);
List < Vertex > path = getShortestPathTo(v);
System.out.println("Path: " + path);
}
}
}```

## Output

```Distance to Delhi: 0.0
Path: [Delhi]
Distance to Mumbai: 5.0
Path: [Delhi, Mumbai]
Distance to chennai: 8.0
Path: [Delhi, Mumbai, chennai]
Distance to Bangalore: 8.0
Path: [Delhi, Bangalore]
Distance to Pune: 10.0
Path: [Delhi, Bangalore, Pune]```