Question

Write a heuristic computer program to solve the shortest path routing problem using the Floyd-Warshall algorithm discussed in the chapter using C++. The user should be able to input the node positions and link costs.

Answer 1

// Hope this code helps you

// If u face any doubt feel free to ask in the comments

// I will be happy to solve them

#include <iostream>
using namespace std;
// defining the number of vertices
#define V 4// You can take any size
#define ll 999// This is infinity or you can say INF short form
void printMatrix(int matrix[][V]);
// Implementing floyd warshall algorithm for shortest path routing
void shortestPathRouting(int graph[][V]) {
  int matrix[V][V], i, j, k;
  for (i = 0; i < V; i++)
    for (j = 0; j < V; j++)
      matrix[i][j] = graph[i][j];
  // Adding vertices
  for (k = 0; k < V; k++) {
    for (i = 0; i < V; i++) {
      for (j = 0; j < V; j++) {
        if (matrix[i][k] + matrix[k][j] < matrix[i][j])
          matrix[i][j] = matrix[i][k] + matrix[k][j];
      }
    }
  }
  printMatrix(matrix);
}
// Printing the matrice
void printMatrix(int matrix[][V]) {
  for (int i = 0; i < V; i++) {
    for (int j = 0; j < V; j++) {
      if (matrix[i][j] == ll)
        printf("%4s", "INF");
      else
        printf("%4d", matrix[i][j]);
    }
    printf("\n");
  }
}
int main() 
{
  int graph[V][V] = {{0, 3, ll, 5},
             {2, 0, ll, 4},
             {ll, 1, 0, ll},
             {ll, ll, 2, 0}};
             cout<<"Shortest path matrix is that contains shortest distance between each pair of node:\n";
  shortestPathRouting(graph);
}

SCREENSHOTS:

Time Complexity

The time complexity of the Floyd-Warshall algorithm is O(n3).

Space Complexity

The space complexity of the Floyd-Warshall algorithm is O(n2).