Scribd
Upload
8 views3 pages

Lab 14

This lab manual provides an introduction to Dijkstra's algorithm for finding the shortest path in a weighted graph, along with a simple Java implementation. It outlines key concepts such as graph representation, priority rules, and the relaxation process, followed by detailed steps and code to execute the algorithm. The manual concludes with a lab task to understand and explain the code line by line.

Uploaded by

ulfat0372
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views3 pages

Lab 14

This lab manual provides an introduction to Dijkstra's algorithm for finding the shortest path in a weighted graph, along with a simple Java implementation. It outlines key concepts such as graph representation, priority rules, and the relaxation process, followed by detailed steps and code to execute the algorithm. The manual concludes with a lab task to understand and explain the code line by line.

Uploaded by

ulfat0372
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Lab Manual 14: Dijkstra's Algorithm

Implementation in Java
Introduction
Dijkstra's algorithm is a popular graph traversal method used to find the shortest path from a
source node to all other nodes in a weighted graph. This manual provides a simple
implementation in Java, suitable for beginners.

1. Algorithm Overview
Key Concepts:

1. Graph Representation: Weighted graphs are represented using adjacency matrices.


2. Priority Rule: Always expand the vertex with the smallest tentative distance.
3. Relaxation: Update the shortest path to a vertex if a shorter path is found through a
neighboring vertex.

Steps:

1. Initialize distances from the source to all vertices as infinite, except for the source itself,
which is 0.
2. Mark all vertices as unvisited.
3. Select the unvisited vertex with the smallest distance and mark it as visited.
4. Update the distances to its neighbors if a shorter path is found.
5. Repeat until all vertices are visited.

Java Implementation
The following code provides a simple implementation of Dijkstra's algorithm:

public class DijkstraAlgorithm {

// Method to find the vertex with the minimum distance that is unvisited
private static int getMinVertex(int[] distances, boolean[] visited) {
int minDistance = Integer.MAX_VALUE;
int minVertex = -1;

for (int i = 0; i < distances.length; i++) {


if (!visited[i] && distances[i] < minDistance) {
minDistance = distances[i];
minVertex = i;
}
}
return minVertex;
}

// Dijkstra's algorithm implementation


public static void dijkstra(int[][] graph, int source) {
int vertices = graph.length;
int[] distances = new int[vertices]; // Shortest distances from
source
boolean[] visited = new boolean[vertices]; // Visited vertices

// Initialize distances to infinity and visited to false


for (int i = 0; i < vertices; i++) {
distances[i] = Integer.MAX_VALUE;
visited[i] = false;
}

// Distance to source is 0
distances[source] = 0;

// Iterate over all vertices


for (int i = 0; i < vertices - 1; i++) {
int u = getMinVertex(distances, visited);

// Mark the picked vertex as visited


visited[u] = true;

// Update distances of adjacent vertices


for (int v = 0; v < vertices; v++) {
if (!visited[v] && graph[u][v] != 0 &&
distances[u] != Integer.MAX_VALUE &&
distances[u] + graph[u][v] < distances[v]) {
distances[v] = distances[u] + graph[u][v];
}
}
}

// Print the distances


System.out.println("Vertex\tDistance from Source");
for (int i = 0; i < vertices; i++) {
System.out.println(i + "\t" + distances[i]);
}
}

// Main method to test the algorithm


public static void main(String[] args) {
// Example graph represented as an adjacency matrix
int[][] graph = {
{0, 10, 20, 0, 0},
{0, 0, 0, 50, 10},
{0, 0, 0, 20, 0},
{0, 0, 0, 0, 60},
{0, 0, 0, 0, 0}
};

int source = 0;
dijkstra(graph, source);
}
}
Explanation

1. Graph Representation: The graph is stored as an adjacency matrix where graph[u][v]


is the weight of the edge from u to v. A value of 0 means no direct edge exists.
2. Initialization: Distances are set to infinity, except for the source, which is 0.
3. Relaxation: Each vertex's distance is updated if a shorter path is found through another
vertex.
4. Output: The shortest distances from the source to all other vertices are printed.

Lab Task:

Understand and run the above code. Explain each line of code in your own words.

You might also like