Floyd’s Warshall Algorithm, C#

Floyd’s Warshall Algorithm

//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Rextester
{
    public class Program
    {
        public static void Main(string[] args)
        {
            /* 
            Floyd’s algorithm is used to find the shortest path between every pair of vertices of a graph. The algorithm works for both directed and un-directed, graphs.
            The Floyd-Warshall algorithm is a shortest path algorithm for graphs. 
            Like the Bellman-Ford algorithm or the Dijkstra's algorithm, it computes the shortest path in a graph. 
            However, Bellman-Ford and Dijkstra are both single-source, shortest-path algorithms. 
            This means they only compute the shortest path from a single source. 
            Floyd-Warshall, on the other hand, computes the shortest distances between every pair of vertices in the input graph.
            */ 
            //Your code goes here
            Console.WriteLine("----  Floyd’s Warshall Algorithm -----");
            
            const int INF = 9999;
            /*
            const int verticesCount = 3;
            int[,] graph = {
                         { 0, 8,  5 },
                         { 2, 0, INF },
                         { INF, 1, 0 },
                       };
            */
            const int verticesCount = 4;
            int[,] graph = {
	                        { 0,   6,  INF, 11 },
	                        { INF, 0,   4, INF },
	                        { INF, INF, 0,   2 },
	                        { INF, INF, INF, 0 }
                           };
            FloydWarshallAlgo fw = new FloydWarshallAlgo();
            fw. FloydWarshall(graph, verticesCount);
            
        }
    }
    
   public class FloydWarshallAlgo
    {
        private const int INF = 9999;
        private void Print(int[,] distance, int verticesCount) {
            Console.WriteLine("Distance Matrix for Shortest Distance between the nodes:");
            for (int i = 0; i < verticesCount; ++i) {
                for (int j = 0; j < verticesCount; ++j) {
                    // // IF THE DISTANCE TO THE NODE IS NOT DIRECTED THAN THE COST IN iNIFINITY
                    if (distance[i, j] == INF)
                        Console.Write("INF".PadLeft(7));
                    else
                        Console.Write(distance[i, j].ToString().PadLeft(7));
                }
                Console.WriteLine();
            }
        }
 
        public void FloydWarshall(int[,] graph, int verticesCount) {
            
            int[,] distance = new int[verticesCount, verticesCount];
 
            // Initialize the distance array
            for (int i = 0; i < verticesCount; ++i) {
                for (int j = 0; j < verticesCount; ++j) {
                    distance[i, j] = graph[i, j];
                }
            }
            // Find shortest path between every pair of vertices of a graph and update distance array with shortest paths
            for (int k = 0; k < verticesCount; ++k) {
                for (int i = 0; i < verticesCount; ++i) {
                    for (int j = 0; j < verticesCount; ++j) {
                        if (distance[i, k] + distance[k, j] < distance[i, j])
                            distance[i, j] = distance[i, k] + distance[k, j];
                    }
                }
            }
 
            Print(distance, verticesCount);
        }

}
}


run \| edit \| history \| help	0