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)

Floyd Warshall Algorithm

We initialize the solution matrix same as the input graph matrix as a first step. Then we update the solution matrix by considering all vertices as an intermediate vertex. The idea is to one by one pick all vertices and update all shortest paths which include the picked vertex as an intermediate vertex in the shortest path. When we pick vertex number k as an intermediate vertex, we already have considered vertices {0, 1, 2, .. k-1} as intermediate vertices. For every pair (i, j) of source and destination vertices respectively, there are two possible cases.

• k is not an intermediate vertex in shortest path from i to j. We keep the value of dist[i][j] as it is.
• k is an intermediate vertex in shortest path from i to j. We update the value of dist[i][j] as dist[i][k] + dist[k][j].

Program in C :

#include<stdio.h>
int min(int,int);
void floyds(int p[10][10],int n)
{
 int i,j,k;
 for(k=1;k<=n;k++)
  for(i=1;i<=n;i++)
   for(j=1;j<=n;j++)
    if(i==j)
     p[i][j]=0;
    else
     p[i][j]=min(p[i][j],p[i][k]+p[k][j]);
}
int min(int a,int b)
{
 if(a<b)
  return(a);
 else
  return(b);
}
void main()
{
 int p[10][10],w,n,e,u,v,i,j;;
 printf("\n Enter the number of vertices:");
 scanf("%d",&n);
 printf("\n Enter the number of edges:\n");
 scanf("%d",&e);
 for(i=1;i<=n;i++)
 {
  for(j=1;j<=n;j++)
   p[i][j]=999;
 }
 for(i=1;i<=e;i++)
 {
  printf("\n Enter the end vertices of edge%d with its weight \n",i);
  scanf("%d%d%d",&u,&v,&w);
  p[u][v]=w;
 }
 printf("\n Matrix of input data:\n");
 for(i=1;i<=n;i++)
 {
  for(j=1;j<=n;j++)
   printf("%d \t",p[i][j]);
  printf("\n");
 }
 floyds(p,n);
 printf("\n Transitive closure:\n");
 for(i=1;i<=n;i++)
 {
  for(j=1;j<=n;j++)
   printf("%d \t",p[i][j]);
  printf("\n");
 }
 printf("\n The shortest paths are:\n");
 for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
  {
   if(i!=j)
    printf("\n <%d,%d>=%d",i,j,p[i][j]);
  }
}

• Output:

Please comment below in case of any problem found during running the code or any other doubts.

Nowadays burning a DVD with ISO image is tidious process, compare to making a Bootable USB. However in market there are plenty of Bootable usb makes such as Pendrive Linux, Unetbootin, Win32DiskImager etc. I have compared all of them and have made more than 300 bootable usb drive.

• Some of them fails to boot or some of them throw error during Operating System installation.

In my experience, Rufus and Win32DiskImager are best Bootable USB maker for any kind of iso(Windows, Ubuntu, Debian, Other linux flavors, Norton Recovery etc). Here is a simple guide to make a bootable USB drive using Rufus :

• Download latest version of Rufus from this link Download
• Double click the exe and run
• When Rufus opens follow only this Two steps:
  • Select the USB Drive in the Device dropdowm
  • Click on the Select image button beside the ISO Image in Dropdown.
  • After you have selected the ISO image some of the settings (like File system, Cluster size) will automatically take optimized value(NO NEED TO CHANGE ANYTHING)

  

  • Then hit Start
• After that is completed, you can reboot and go to BIOS to boot from USB device.

For making bootable iso from Ubuntu or any other linux you may use UnetBootin.

• Goto this page for downloading required flavor of UnetBootin Download
• Then just follow the image below as selected Please comment below in case of any problem found during running the code or any other doubts.