DAA P6 flyod warshall

-

 Floyd Warshal

// C++ Program for Floyd Warshall Algorithm
#include <bits/stdc++.h>
using namespace std;

// Number of vertices in the graph
#define V 4

/* Define Infinite as a large enough
value.This value will be used for
vertices not connected to each other */
#define INF 99999

// A function to print the solution matrix
void printSolution(int dist[][V]);

// Solves the all-pairs shortest path
// problem using Floyd Warshall algorithm
void floydWarshall(int dist[][V])
{

  int i, j, k;

  /* Add all vertices one by one to
  the set of intermediate vertices.
  ---> Before start of an iteration,
  we have shortest distances between all
  pairs of vertices such that the
  shortest distances consider only the
  vertices in set {0, 1, 2, .. k-1} as
  intermediate vertices.
  ----> After the end of an iteration,
  vertex no. k is added to the set of
  intermediate vertices and the set becomes {0, 1, 2, ..
  k} */
  for (k = 0; k < V; k++) {
    // Pick all vertices as source one by one
    for (i = 0; i < V; i++) {
      // Pick all vertices as destination for the
      // above picked source
      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][j] > (dist[i][k] + dist[k][j])
          && (dist[k][j] != INF
            && dist[i][k] != INF))
          dist[i][j] = dist[i][k] + dist[k][j];
      }
    }
  }

  // Print the shortest distance matrix
  printSolution(dist);
}

/* A utility function to print solution */
void printSolution(int dist[][V])
{
  cout << "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)
        cout << "INF"
          << " ";
      else
        cout << dist[i][j] << " ";
    }
    cout << endl;
  }
}

// Driver's code
int main()
{
  /* Let us create the following weighted graph
      10
  (0)------->(3)
    |  /|\
  5 |  |
    |  | 1
  \|/  |
  (1)------->(2)
      3  */
  int graph[V][V] = { { 0, 5, INF, 10 },
            { INF, 0, 3, INF },
            { INF, INF, 0, 1 },
            { INF, INF, INF, 0 } };

  // Function call
  floydWarshall(graph);
  return 0;
}

Comments

Post a Comment

Popular posts from this blog

DAA P4 bfs, dfs

-
BFS #include < bits/stdc++.h > using namespace std ; class Graph {   int V ;   vector < list <int> > adj ; public :   Graph ( int V );   void addEdge ( int v , int w );   void BFS ( int s ); }; Graph :: Graph ( int V ) {   this -> V = V ;   adj . resize ( V ); } void Graph :: addEdge ( int v , int w ) {   adj [ v ] . push_back ( w ); } void Graph :: BFS ( int s ) {   vector <bool> visited ;   visited . resize ( V , false );   list <int> queue ;   visited [ s ] = true ;   queue . push_back ( s );   while ( ! queue . empty ()) {         s = queue . front ();     cout << s << " " ;     queue . pop_front ();     for ( auto adjacent : adj [ s ] ) {       if ( ! visited [ adjacent ] ) {         visited [ adjacent ] = true ;         q...
Read more

DAA P8 graph coloring

-
  Graph coloring // A C++ program to implement greedy algorithm for graph coloring #include < iostream > #include < list > using namespace std ; // A class that represents an undirected graph class Graph {   int V ; // No. of vertices   list <int> * adj ; // A dynamic array of adjacency lists public :   // Constructor and destructor   Graph ( int V ) { this -> V = V ; adj = new list <int> [ V ]; }   ~Graph ()   { delete [] adj ; }   // function to add an edge to graph   void addEdge ( int v , int w );   // Prints greedy coloring of the vertices   void greedyColoring (); }; void Graph :: addEdge ( int v , int w ) {   adj [ v ]. push_back ( w );   adj [ w ]. push_back ( v ); // Note: the graph is undirected } // Assigns colors (starting from 0) to all vertices and prints // the assignment of colors void Graph :: greedyColoring () {   int result [ V ];   //...
Read more

Practical 8 by Karan

-
 #include <stdio.h> struct emp { int no; int sal; char name[20]; };   int binarySearch(struct emp a[], int n, int x) {        int low=0, mid, high=n-1, count = 0;    while(low <= high)    {        count++;         mid = (low + high) / 2;         if (x < a[mid].no)             high = mid - 1;         else if (x > a[mid].no)          low = mid + 1;        else {         printf("no of search = %d\n",count);       return mid;        }    } return -1; }    void printArray(struct emp array[], int size) {   for (int i = 0; i < size; ++i) {      printf("name = %s\n",array[i].name);     printf(" salary = %d\n ", array[i].sal);      printf(" number = %d...
Read more