# Program for Dijkstra's Algorithm

0 like 0 dislike
508 views

From a given vertex in a weighted connected graph, find shortest paths to other vertices using Dijkstra's algorithm. Write the program in Java.

### For Indian Students- INR 570/- || For International Students- \$12.99/-

S.No.

Course Name

Apply Coupon

1.

Tensorflow 2 & Keras:Deep Learning & Artificial Intelligence

Apply Coupon

2.

Computer Vision with OpenCV | Deep Learning CNN Projects

Apply Coupon

3.

Complete Machine Learning & Data Science with Python Apply Coupon

4.

Natural Language Processing-NLP with Deep Learning in Python Apply Coupon

5.

Computer Vision OpenCV Python | YOLO| Deep Learning in Colab Apply Coupon

6.

Complete Python Programming from scratch with Projects Apply Coupon

0 like 0 dislike
by Goeduhub's Expert (5.8k points)

Java Program

import java.util.*;

// Data structure to store graph edges

class Edge

{

int source, dest, weight;

public Edge(int source, int dest, int weight) {

this.source = source;

this.dest = dest;

this.weight = weight;

}

};

// Data structure to store heap nodes

class Node {

int vertex, weight;

public Node(int vertex, int weight) {

this.vertex = vertex;

this.weight = weight;

}

};

// class to represent a graph object

class Graph

{

// A List of Lists to represent an adjacency list

// Constructor

Graph(List<Edge> edges, int N)

{

for (int i = 0; i < N; i++) {

}

// add edges to the undirected graph

for (Edge edge: edges) {

}

}

}

class Dijk

{

private static void getRoute(int prev[], int i, List<Integer> route)

{

if (i >= 0) {

getRoute(prev, prev[i], route);

}

}

// Run Dijkstra's algorithm on given graph

public static void shortestPath(Graph graph, int source, int N)

{

// create min heap and push source node having distance 0

PriorityQueue<Node> minHeap = new PriorityQueue<>(Comparator.comparingInt(node -> node.weight));

// set infinite distance from source to v initially

List<Integer> dist = new ArrayList<>(Collections.nCopies(N, Integer.MAX_VALUE));

// distance from source to itself is zero

dist.set(source, 0);

// boolean array to track vertices for which minimum

boolean[] done = new boolean[N];

done[source] = true;

// stores predecessor of a vertex (to print path)

int prev[] = new int[N];

prev[source] = -1;

List<Integer> route = new ArrayList<>();

// run till minHeap is not empty

while (!minHeap.isEmpty())

{

// Remove and return best vertex

Node node = minHeap.poll();

// get vertex number

int u = node.vertex;

// do for each neighbor v of u

{

int v = edge.dest;

int weight = edge.weight;

// Relaxation step

if (!done[v] && (dist.get(u) + weight) < dist.get(v))

{

dist.set(v, dist.get(u) + weight);

prev[v] = u;

}

}

// marked vertex u as done so it will not get picked up again

done[u] = true;

}

for (int i = 1; i < N; ++i)

{

if (i != source && dist.get(i) != Integer.MAX_VALUE) {

getRoute(prev, i, route);

System.out.printf("Path (%d -> %d): Minimum Cost = %d and Route is %s\n", source, i, dist.get(i), route);

route.clear();

}

}

}

public static void main(String[] args)

{

// initialize edges as per above diagram

// (u, v, w) triplet represent undirected edge from

// vertex u to vertex v having weight w

List<Edge> edges = Arrays.asList(

new Edge(0, 1, 10), new Edge(0, 4, 3),

new Edge(1, 2, 2), new Edge(1, 4, 4),

new Edge(2, 3, 9), new Edge(3, 2, 7),

new Edge(4, 1, 1), new Edge(4, 2, 8),

new Edge(4, 3, 2)

);

// Set number of vertices in the graph

final int N = 5;

// construct graph

Graph graph = new Graph(edges, N);

int source = 0;

shortestPath(graph, source, N);

}

}

Output 