Analysis of Algorithms (AOA)

All Pairs Shortest Path in C++

/*
	Program for All Pairs Shortest Path in C++
	Author: PracsPedia		www.pracspedia.com
*/
#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>

class shortest
{
	private:
	int n,e;
	float cost[20][20],A[20][20];
	public:
	void readedges();
	void AllShortestPaths();
	void disp();
};

void shortest::disp()
{
	int i,j;
	cout<<"new distance matrix\n";
	for(i=1;i <= n;i++)
	{
		for(j=1;j <= n;j++)
		{
			cout<<A[i][j]<<"\t";
		}
		cout<<"\n\n";
	}
}

void shortest::readedges()
{
	int i,j,v1,v2;
	cout<<"enter no of vertices\n";
	cin>>n;
	for(i=1;i <= n;i++)
	{
		for(j=1;j <= n;j++)
			cost[i][j]=9999;
		cost[i][i]=0;
	}
	cout<<"Enter total no.of edges\n";
	cin>>e;
	for(i=1;i <= e;i++)
	{
		cout<<"enter the edge(starting vertex-ending vertex)\n";
		cin>>v1>>v2;
		cout<<"enter cost\n";
		cin>>cost[v1][v2];
	}
}
void shortest::AllShortestPaths()
{
	int i,j,k;
	for(i=1;i <= n;i++)
		for(j=1;j <= n;j++)
			A[i][j]=cost[i][j];

	for(k=1;k <= n;k++)
	{
		for(i=1;i <= n;i++)
		{
			for(j=1;j <= n;j++)
			{
				if(A[i][j] > (A[i][k]+A[k][j]))
				{
					A[i][j]=A[i][k]+A[k][j];
				}
			}
		}
		disp();
	}
}

void main()
{
	int v,i;
	shortest s;
	clrscr();
	s.readedges();
	s.AllShortestPaths();
	getch();
}
Download Source Code Program List

Sample Output

all pairs shortest path output
all pairs shortest path output