PART A

(PART A : TO BE REFFERED BY STUDENTS)

Experiment No. 06
A.1 Aim:
Write a program to implement all pair shortest path using Dynamic Programming
Approach.

A.2 Prerequisite: -

A.3 Outcome:

After successful completion of this experiment students will be able to solve a problem by
applying dynamic programming approach. A.4 Theory:

The Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph
with positive or negative edge weights (but with no negative cycles). A single execution
of the algorithm will find the lengths (summed weights) of the shortest paths between all
pairs of vertices, though it does not return details of the paths themselves.
Versions of the algorithm can also be used for finding the transitive closure of a relation
, or (in connection with the Schulze voting system) widest paths between all pairs of
vertices in a weighted graph.

The Floyd–Warshall algorithm is an example of dynamic programming, The algorithm is

also known as Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm,
or the WFI algorithm.

Algorithm:

let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity) for

each vertex v

dist[v][v] ← 0 for each edge (u,v)

dist[u][v] ← w(u,v) // the weight of the edge (u,v)

for k from 1 to |V|

for i from 1 to |V|

 for j from 1 to |V|

if dist[i][j] > dist[i][k] + dist[k][j]

dist[i][j] ← dist[i][k] + dist[k][j] end

if

Example:

The algorithm is executed on the graph on the below:

Time Complexity:

First double for loop = O(n^2)

Nested 3 for loop = O(n^3)

PART B
(PART B : TO BE COMPLETED BY STUDENTS)
(Students must submit the soft copy as per following segments within two
hours of the practical. The soft copy must be uploaded on the Blackboard
or emailed to the concerned lab in charge faculties at the end of the
practical in case the there is no Black board access available)

Roll No.: B60 Name: Rajshree Rajendra Dandge

Class: SE Batch: B3
Date of Experiment: 08-03-2025 Date of Submission: 09-03-2025
Grade:
B.1 Software Code written by student:
(Paste your code completed during the 2 hours of practical in the lab here)

#include <stdio.h>

#include <limits.h>

// Number of vertices in the graph

#define V 4

// Define infinity as a large value

#define INF INT_MAX

// Function to print the solution matrix void

printSolution(int dist[V][V]);

// Function to implement the Floyd-Warshall algorithm void

floydWarshall(int graph[V][V]) { int dist[V][V]; // dist[i][j] will hold

the shortest distance from i to j

// Initialize the solution matrix same as input graph matrix

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

for (int j = 0; j < V; j++) {

dist[i][j] = graph[i][j];

// Add all vertices one by one to the set of intermediate vertices

for (int k = 0; k < V; k++) {

 // Pick all vertices as source one by one

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

// Pick all vertices as destination for the above-picked source

for (int j = 0; j < V; j++) {

// If vertex k is on the shortest path from i to j, then update dist[i][j]

if (dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] = dist[i][k] + dist[k][j];

// Print the shortest distance matrix

printSolution(dist);

// Function to print the solution matrix void printSolution(int dist[V][V]) { printf("The following

matrix shows the shortest distances between every pair of vertices\n");

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

for (int j = 0; j < V; j++) {

if (dist[i][j] == INF)

{ printf("%7s", "INF");

} else { printf("%7d",

dist[i][j]);

} }

printf("\n");

}
int main() { int graph[V][V] =

{{0, 3, INF, 7},

{8, 0, 2, INF},

{5, INF, 0, 1},

{2, INF, INF, 0}};

floydWarshall(graph);

return 0;

B.2 Input and Output:

B.3 Observations and learning:

B.4 Conclusion:

B.5 Question of Curiosity

(To be answered by student based on the practical performed and
learning/observations)

Q1: What are different algorithms available to find shortest path?

Dijkstra's Algorithm:

• Use Case: Finds the shortest path from a single source vertex to all
other vertices in a graph with non-negative weights.
• Complexity: O(V2)O(V^2) for the simplest implementation, and
O(Elog⁡V)O(E \log V) with a priority queue (using a binary heap).

Bellman-Ford Algorithm:

• Use Case: Finds the shortest path from a single source vertex to all
other vertices and handles graphs with negative weights.

• Complexity: O(V×E)O(V \times E).

Floyd-Warshall Algorithm:

• Use Case: Finds the shortest paths between all pairs of vertices (all-
pairs shortest path) in a graph.

• Complexity: O(V3)O(V^3).

A\ Search Algorithm:*

• Use Case: Finds the shortest path between two specific nodes using
heuristics to improve performance, often used in AI for pathfinding.

• Complexity: Depends on the heuristic, but generally performs better

than Dijkstra's in practice.

Johnson's Algorithm:

• Use Case: Finds shortest paths between all pairs of vertices in sparse
graphs and handles negative weights.

• Complexity: O(V2log⁡V+VE)O(V^2 \log V + VE).

Bidirectional Search:

• Use Case: Finds the shortest path between two specific nodes by
simultaneously searching from the start node and the goal node.

• Complexity: Improves over single-source shortest path algorithms,

especially in large graphs.

BFS (Breadth-First Search):

• Use Case: Finds the shortest path in unweighted graphs or graphs

where all edge weights are the same.

• Complexity: O(V+E)O(V + E).

 SPFA (Shortest Path Faster Algorithm):

• Use Case: An improvement over the Bellman-Ford algorithm, often

faster in practice for finding single-source shortest paths in graphs with
negative weights.

• Complexity: Varies, but can be as fast as O(E)O(E) on average.

Q2: Derive time complexity of Floyd’s algorithm?

Time Complexity Analysis:

1. Initialization:

o Initializing the distance matrix dist[][] with the edge weights

takes O(V2)O(V^2) time, where VV is the number of vertices.

2. Main Loops:

o The algorithm uses three nested loops to update the shortest

path estimates. Each loop runs from 1 to VV, where VV is the
number of vertices.

The loops can be broken down as follows:

• The outermost loop runs VV times.

• The middle loop runs VV times for each iteration of the outermost

loop. • The innermost loop runs VV times for each iteration of the

middle loop.

Thus, the total number of iterations for the innermost statement is

V×V×V=V3V \times V \times V = V^3.

3. Innermost Statement:

o In the innermost loop, the algorithm performs a constant-time

comparison and update operation (dist[i][j] > dist[i][k] + dist[k]
[j]).

Since the innermost statement is executed V3V^3 times, and each

execution takes O(1)O(1) time, the total time complexity for the Floyd-
Warshall algorithm is:

O(V3)
 Q3: Compare Floyd’s algorithm with other algorithms?

Floyd-Warshall vs. Dijkstra:

• Floyd-Warshall finds shortest paths between all pairs of vertices, while

Dijkstra finds shortest paths from a single source vertex to all other
vertices.

• Floyd-Warshall has cubic complexity O(V3)O(V^3), making it less

suitable for large graphs compared to Dijkstra's O(V2)O(V^2) or
O(Elog⁡V)O(E \log V).

Floyd-Warshall vs. Bellman-Ford:

• Floyd-Warshall is used for all-pairs shortest paths, whereas Bellman-

Ford is used for single-source shortest paths.

• Floyd-Warshall has O(V3)O(V^3) complexity, whereas Bellman-Ford has

O(V×E)O(V \times E) complexity, making Bellman-Ford potentially faster
for sparse graphs.

• Both algorithms handle negative edge weights, but Floyd-Warshall does

not detect negative weight cycles, while Bellman-Ford does.

Q4: Explain application areas of all pair shortest path algorithm.

Network Routing:

• Internet and Telecommunications: Efficiently managing data packet

routing by determining the shortest paths between all nodes in a
network, ensuring minimal latency and optimal bandwidth utilization.

• Traffic Management: Optimizing routes in vehicular networks, such as

determining the shortest paths for data transmission in vehicular ad-
hoc networks (VANETs).

2. Geographic Information Systems (GIS):

• Urban Planning: Planning and analyzing transportation systems,

including road networks, public transportation routes, and pedestrian
pathways.
 • Navigation Systems: Providing the shortest path information for GPS
devices and navigation software to guide users to their destinations
efficiently.

3. Transportation and Logistics:

• Supply Chain Management: Optimizing delivery routes and logistics

planning to minimize transportation costs and delivery times.

• Airline Scheduling: Finding the most efficient flight paths and

scheduling for airlines to reduce fuel consumption and improve on-time
performance.

************************