- Get link
- Other Apps

### Featured Post

Posted by
Varun
on

- Get link
- Other Apps

### Purpose

- Finds the shortest paths from a single source vertex to all other vertices in a weighted graph.
- Commonly used in GPS navigation, network routing, and logistics planning.

### Key Concepts

- Weighted Graph: A set of vertices (nodes) connected by edges with associated weights (distances, costs, etc.).
- Source Vertex: The starting point for finding shortest paths.
- Shortest Path: The path with the minimum total weight between two vertices.

### Algorithm Steps

Initialization:

- Create a set
`S`

to store visited vertices (initially empty). - Initialize an array
`distances`

with infinite values for all vertices except the source, which is set to 0. - Create a priority queue
`Q`

to store vertices, prioritized by their tentative distances. - Add the source vertex to
`Q`

.

- Create a set
Exploration Loop:

- While
`Q`

is not empty:- Extract the vertex
`u`

with the minimum distance from`Q`

. - Add
`u`

to the set`S`

(mark as visited). - For each neighbor vertex
`v`

of`u`

:- If
`v`

is not visited and the distance to`v`

through`u`

is shorter than its current distance:- Update the distance to
`v`

in the`distances`

array. - Add
`v`

to the priority queue`Q`

(or update its priority if already present).

- Update the distance to

- If

- Extract the vertex

- While
Result:

- The
`distances`

array now contains the shortest distances from the source vertex to all other vertices. - To reconstruct the actual shortest paths, keep track of the predecessor of each vertex during the exploration.

- The

```
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.stream.Collectors;
public class Dijkstra {
public static List
``` dijkstra(Graph graph, int source) {
int[] distances = new int[graph.numVertices];
Arrays.fill(distances, Integer.MAX_VALUE);
distances[source] = 0;
PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(i -> distances[i]));
pq.offer(source);
boolean[] visited = new boolean[graph.numVertices];
while (!pq.isEmpty()) {
int u = pq.poll();
visited[u] = true;
for (Edge edge : graph.adjacencyList.get(u)) {
int v = edge.to;
int weight = edge.weight;
if (!visited[v] && distances[u] + weight < distances[v]) {
distances[v] = distances[u] + weight;
pq.offer(v);
}
}
}
return Arrays.stream(distances).boxed().collect(Collectors.toList());
}
public static Graph createRandomGraph(int numVertices) {
Graph graph = new Graph(numVertices);
Random random = new Random();
// Add edges with random weights
for (int i = 0; i < 9; i++) {
for (int j = i + 1; j < 9; j++) {
// Decide whether to create an edge with 50% probability
if (random.nextBoolean()) {
int weight = random.nextInt(10) + 1; // Random weight between 1 and 10
graph.addEdge(i, j, weight);
graph.addEdge(j, i, weight); // Add reverse edge for undirected graph (if needed)
}
}
}
return graph;
}
public static void main(String[] args) {
// Create a sample graph
Graph graph = createRandomGraph(9);
graph.visualize();
int source = 0;
List distances = dijkstra(graph, source);
System.out.println("Shortest distances from " + source + ": " + distances);
}
public static class Edge {
int to;
int weight;
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
public static class Graph {
int numVertices;
List> adjacencyList;
Graph(int numVertices) {
this.numVertices = numVertices;
adjacencyList = new ArrayList<>();
for (int i = 0; i < numVertices; i++) {
adjacencyList.add(new ArrayList<>());
}
}
void addEdge(int from, int to, int weight) {
adjacencyList.get(from).add(new Edge(to, weight));
}
void visualize() {
System.out.println("Graph Visualization:\n");
for (int vertex = 0; vertex < numVertices; vertex++) {
System.out.print(vertex + " -> ");
for (Edge edge : adjacencyList.get(vertex)) {
System.out.print(edge.to + "(" + edge.weight + ") ");
}
System.out.println();
}
}
}
}

## Explanation of code

#### Graph Representation

- The
`Graph`

class models a graph using an adjacency list, where each vertex stores a list of its connected edges and their weights. - The
`Edge`

class encapsulates the destination vertex and weight of an edge.

- The
#### Dijkstra's Algorithm Implementation

- The
`dijkstra(Graph, source)`

method implements the algorithm's logic:- It maintains a priority queue to explore vertices in order of their tentative distances.
- It iteratively relaxes edges to update distances and explore reachable vertices.
- It ultimately returns a list of the shortest distances from the source vertex to all other vertices.

- The
#### Random Graph Generation

- The
`createRandomGraph(numVertices)`

method generates a graph with a specified number of vertices and randomly assigns edges with weights between 1 and 10.

- The

- Get link
- Other Apps

## Comments

## Post a Comment

Please post your valuable suggestions