Scribd
Upload
4 views3 pages

Shortest Path Algorithms Assignment

The document discusses shortest path algorithms, focusing on Single Source Shortest Path (SSSP) and All-Pairs Shortest Path (APSP) algorithms. It details Dijkstra's and Bellman-Ford algorithms for SSSP, and the Floyd-Warshall algorithm for APSP, highlighting their applications and processes. The conclusion emphasizes the importance of these algorithms in real-world scenarios like GPS navigation and logistics.

Uploaded by

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

Shortest Path Algorithms Assignment

The document discusses shortest path algorithms, focusing on Single Source Shortest Path (SSSP) and All-Pairs Shortest Path (APSP) algorithms. It details Dijkstra's and Bellman-Ford algorithms for SSSP, and the Floyd-Warshall algorithm for APSP, highlighting their applications and processes. The conclusion emphasizes the importance of these algorithms in real-world scenarios like GPS navigation and logistics.

Uploaded by

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

Assignment: Shortest Path Algorithms

Course Title: Algorithm Lab


Course Code: 0613-206
Submitted To: Abdullah All Mamun, Lecturer, Dept. of CSE
Submitted By: Masudur Rahman
Roll: 33
Reg. No.: CS-D-86-22-123494
Submission Date: June 15, 2025

1. Single Source Shortest Path (SSSP) Algorithm


The Single Source Shortest Path algorithm helps find the minimum cost path from a
given source vertex to every other vertex in a weighted graph. It's widely used in routing
and navigation systems.

1.1 Algorithms
There are two major algorithms used for SSSP:

1. Dijkstra's Algorithm – used when all edge weights are non-negative.

2. Bellman-Ford Algorithm – supports graphs with negative weights.

1.2 Dijkstra's Algorithm


Dijkstra’s algorithm uses a greedy strategy to always pick the nearest unvisited vertex.

Step-by-step Process:

1. Assign all distances as ∞, except the source node (set to 0).

2. Use a priority queue (or min-heap) to track vertices with the minimum tentative
distance.

3. Update the distances of neighbors if a shorter path is found.

4. Repeat until all vertices are finalized.


Example Graph:
Vertices: A, B, C, D
Edges: A-B(4), A-C(2), C-B(1), B-D(5), C-D(8)

Visual Representation:

Use the following code at: [Link]

graph Dijkstra {
A -- B [label=4];
A -- C [label=2];
C -- B [label=1];
B -- D [label=5];
C -- D [label=8];
}

Dijkstra's Output from Source A:


A→A=0
A→C=2
A → B = 3 (via C)
A → D = 8 (via B)

1.3 Bellman-Ford Algorithm


Unlike Dijkstra, Bellman-Ford works for graphs with negative edge weights. It relaxes
each edge |V| - 1 times.

Its time complexity is O(V × E).

2. All-Pairs Shortest Path (APSP) Algorithm


While SSSP finds the shortest paths from one source, APSP helps find the shortest paths
between every pair of nodes.

2.1 Floyd-Warshall Algorithm


Floyd-Warshall is a dynamic programming approach to compute the shortest paths
between all node pairs.

It works for both positive and negative weights (no negative cycles).

Step-by-step Process:

1. Initialize a matrix with distances. Set diagonal values to 0.


2. For every intermediate vertex k, update: D[i][j] = min(D[i][j], D[i][k] + D[k][j])

Example Graph:
Vertices: A, B, C
Edges: A→B (3), B→C (1), A→C (∞)

Initial Matrix:

A B C
A[0 3 ∞]
B[∞ 0 1]
C[∞ ∞ 0]

After running Floyd–Warshall:

A B C
A[0 3 4]
B[∞ 0 1]
C[∞ ∞ 0]

You can visualize this graph using the following Graphviz code:

digraph APSP {
A -> B [label=3];
B -> C [label=1];
}

3. Conclusion
Shortest path algorithms are vital for solving real-world problems such as GPS
navigation, packet routing, and logistics. Dijkstra’s is fast for graphs with non-negative
weights, Bellman-Ford allows negative weights, and Floyd-Warshall gives us a global
view of shortest paths between all node pairs. Understanding these allows developers and
researchers to make optimal choices for solving network and path optimization
challenges.

You might also like