🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.
▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube
▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube
1. Introduction
The Floyd-Warshall algorithm is a dynamic programming technique used to solve the all-pairs shortest path problem. The problem is to find the shortest distances between every pair of vertices in a given edge-weighted directed graph. This algorithm works for both positive and negative weights.
2. Program Overview
In this program, we will:
1. Implement the Floyd-Warshall algorithm.
2. Calculate the shortest distance between every pair of vertices in the provided graph.
3. Code Program
#include<stdio.h>
// Number of vertices in the graph
#define V 4
// A function to print the solution matrix
void printSolution(int dist[][V]);
void floydWarshall (int graph[][V])
{
int dist[V][V], i, j, k;
// Initialize the solution matrix same as input graph matrix.
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
dist[i][j] = graph[i][j];
// Update the solution matrix by picking all vertices one by one
for (k = 0; k < V; k++)
{
for (i = 0; i < V; i++)
{
for (j = 0; j < V; j++)
{
// If vertex k is on the shortest path from i to j,
// then update the value of dist[i][j]
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
printSolution(dist);
}
void printSolution(int dist[][V])
{
printf ("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] == 9999)
printf("%7s", "INF");
else
printf ("%7d", dist[i][j]);
}
printf("\n");
}
}
int main()
{
int graph[V][V] = { {0, 5, 9999, 10},
{9999, 0, 3, 9999},
{9999, 9999, 0, 1},
{9999, 9999, 9999, 0}
};
floydWarshall(graph);
return 0;
}
Output:
Following matrix shows the shortest distances between every pair of vertices
0 5 8 9
INF 0 3 4
INF INF 0 1
INF INF INF 0
4. Step By Step Explanation
1. The algorithm works by repeatedly exploring paths between every pair using all possible intermediate vertices.
2. We start by creating a dist matrix and initialize it the same as the input graph matrix.
3. We then update the solution matrix by considering each vertex and updating all shortest paths which include the picked vertex as an intermediate vertex.
4. After the main procedure, we print the distance matrix. Note that the value 9999 in the program is considered as "INFINITY", i.e., a path between these vertices doesn't exist.
The algorithm uses a triple nested loop that iterates through each combination of vertices. Its time complexity is O(V^3), where V is the number of vertices in the graph.
My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:
Build REST APIs with Spring Boot 4, Spring Security 7, and JWT
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment