6 Replies - 1518 Views - Last Post: 28 October 2012 - 01:07 PM Rate Topic: -----

#1 bcnafegar  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 31
  • Joined: 13-May 11

Floyd's algorithm

Posted 27 October 2012 - 11:04 AM

I have to read in a matrix and use Floyd's algorithm to find the shortest path

#include <iomanip>
#include <fstream>
#include<string>
#include <iostream>
#include<algorithm>
#include <vector>
#include <iterator>
using namespace std;


int main()
{
	vector<int> vertices;
	vector<int>::iterator element;
	vector<int>edges;
	int next;
	int vert;
	int  temp;
	int weight[20][20];
	//int *weight;
	int path[20][20];
	int copy[20][20];
	int edge[20][20];	
	int i,j;
	string filename;
	ifstream file;
	cout<<"Please enter the path and file name "<<endl;
	cin>>filename;
	
	file.open(filename);
	file>>vert;
	cout<<"Input matrix M : "<<endl;
	while (!file.eof())
	{
		for (i =0; i < vert;i++)
		{
			for (j=0;j<vert;j++)
			{
				
				file>>weight[i][j];
				copy[i][j]=weight[i][j];
				cout<<weight[i][j]<<" ";//original matrix		
			//	cout<<copy[i][j]<<" ";
			}
			cout<<'\n';			
		}
	}
	cout<<"HERE "<<weight[0][3]<<endl;
	for (i =0; i < vert;i++)
		{
			for (j=0;j<vert;j++)
			{
				
				path[i][j]=0;	
				//cout<<path[i][j]<<" ";
			}
			//cout<<'\n';			
		}
	//cout<<endl<<endl;
	//int floyds(int *weight)
	//{

	for(i=0;i<=vert;i++)
	 for(j=0; j<=vert;j++)
		copy[i][j]=0;


	/*for(i=0;i<=vert;i++)
	 for(j=0; j<=vert;j++)
		 if (weight[i][j] ==-1)
			 weight[i][j]=9999999;*/




	for(int k=0;k<vert;k++)
	{
		
					 for(i=0; i<vert;i++)		 
						for(j=0; j<vert;j++) 
						{
						 
								if (((weight[i][k] * weight [k][j]) !=0) && (i!=j))
								{
									//{
										if (((weight[i][k] + weight[k][j]) < weight[i][j]) || (weight[i][j] ==0))
										{
												weight[i][j] =  weight[i][k] + weight[k][j];
										
												path[i][j] = k;
										}	
									//}
								}
			
						}
		 
						 
		 
	}
	 
	
	
	
	cout<<"Weight matrix "<<endl;
	for (i =0; i < vert;i++)
		{
			for (j=0;j<vert;j++)
			{
				
					
				cout<<weight[i][j]<<" ";
			}
			cout<<'\n';			
		}
	cout<<endl<<endl;
	cout<<"COPY  "<<endl;
	for (i =0; i < vert;i++)
		{
			for (j=0;j<vert;j++)
			{
				
					
				cout<<copy[i][j]<<" ";
			}
			cout<<'\n';			
		}
	cout<<endl<<endl;
	cout<<"PATH "<<endl;
	for (i =0; i < vert;i++)
		{
			for (j=0;j<vert;j++)
			{
				
					
				cout<<path[i][j]<<" ";
			}
			cout<<'\n';			
		}
	


	cout<<endl;


		cin.get(),cin.get();
	return 0;
}


		



I've gone by the algorithm but the output is incorrect, it should be
0 2 2 4
-1 0 2 3
-1 -1 0 2
-1 -1 -1 0

Is This A Good Question/Topic? 0
  • +

Replies To: Floyd's algorithm

#2 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6058
  • View blog
  • Posts: 23,496
  • Joined: 23-August 08

Re: Floyd's algorithm

Posted 27 October 2012 - 11:21 AM

And what is the output you're receiving?
Was This Post Helpful? 0
  • +
  • -

#3 bcnafegar  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 31
  • Joined: 13-May 11

Re: Floyd's algorithm

Posted 27 October 2012 - 11:32 AM

0 -3 -2 -1
-5 0 -3 -2
-6 -5 0 -3
-3 -2 -1 0

I've fiddled with it and have gotten different results but this result is directly from the code posted. I'm just confused because I've followed the algorithm basically and arent getting what i would think...
Was This Post Helpful? 0
  • +
  • -

#4 jimblumberg  Icon User is online

  • member icon


Reputation: 4025
  • View blog
  • Posts: 12,432
  • Joined: 25-December 09

Re: Floyd's algorithm

Posted 27 October 2012 - 12:20 PM

What are you inputting into your program?

Jim
Was This Post Helpful? 0
  • +
  • -

#5 bcnafegar  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 31
  • Joined: 13-May 11

Re: Floyd's algorithm

Posted 27 October 2012 - 12:21 PM

#include <iomanip>
#include <fstream>
#include<string>
#include <iostream>
#include<algorithm>
#include <vector>
#include <iterator>
using namespace std;


int main()
{
	vector<int> vertices;
	vector<int>::iterator element;
	vector<int>edges;
	int next;
	int vert;
	int  temp;
	int weight[20][20];
	//int *weight;
	int path[20][20];
	int copy[20][20];
	int edge[20][20];	
	int i,j;
	string filename;
	ifstream file;
	cout<<"Please enter the path and file name "<<endl;
	cin>>filename;
	
	file.open(filename);
	file>>vert;
	cout<<"Input matrix M : "<<endl;
	while (!file.eof())
	{
		for (i =0; i < vert;i++)
		{
			for (j=0;j<vert;j++)
			{
				
				file>>weight[i][j];
				copy[i][j]=weight[i][j];
				cout<<weight[i][j]<<" ";//original matrix		
			//	cout<<copy[i][j]<<" ";
			}
			cout<<'\n';			
		}
	}
	cout<<"HERE "<<weight[0][3]<<endl;
	for (i =0; i < vert;i++)
		{
			for (j=0;j<vert;j++)
			{
				
				path[i][j]=0;	
				//cout<<path[i][j]<<" ";
			}
			//cout<<'\n';			
		}
	//cout<<endl<<endl;
	//int floyds(int *weight)
	//{

	for(i=0;i<=vert;i++)
	 for(j=0; j<=vert;j++)
		copy[i][j]=0;


	for(i=0;i<=vert;i++)
	 for(j=0; j<=vert;j++)
		 if (weight[i][j] ==-1)
			 weight[i][j]=9999999;




	for(int k=0;k<vert;k++)
	{
		
					 for(i=0; i<vert;i++)	
					 {
						for(j=0; j<vert;j++) 
						{
						 
								if (((weight[i][k] * weight [k][j]) !=0) && (i!=j))
								{
									//{
										if ((	(weight[i][k] + weight[k][j]) < (weight[i][j])) || (weight[i][j] ==0 ))
										{
												weight[i][j] =  weight[i][k] + weight[k][j];
										
												path[i][j] = k;
										}	
										else 
											weight [i][j]=weight[i][j];
									//}
								}
						}
						}
		 
						 
		 
	}
	 for(i=0;i<=vert;i++)
	 for(j=0; j<=vert;j++)
		 if (weight[i][j] ==9999999)
			 weight[i][j]=-1;
	
	
	
	cout<<"Weight matrix "<<endl;
	for (i =0; i < vert;i++)
		{
			for (j=0;j<vert;j++)
			{
				
					
				cout<<weight[i][j]<<" ";
			}
			cout<<'\n';			
		}
	cout<<endl<<endl;
	cout<<"COPY  "<<endl;
	for (i =0; i < vert;i++)
		{
			for (j=0;j<vert;j++)
			{
				
					
				cout<<copy[i][j]<<" ";
			}
			cout<<'\n';			
		}
	cout<<endl<<endl;
	cout<<"PATH "<<endl;
	for (i =0; i < vert;i++)
		{
			for (j=0;j<vert;j++)
			{
				
					
				cout<<path[i][j]<<" ";
			}
			cout<<'\n';			
		}
	


	cout<<endl;


		cin.get(),cin.get();
	return 0;
}






0 2 2 4
-1 0 2 3
-1 -1 0 2
-1 -1 -1 0
I now get this result from the new code, but I need to get this for the path matrix
0 0 0 3
0 0 0 0
0 0 0 0
0 0 0 0

but instead i get a 2 instead of a 3...
Was This Post Helpful? 0
  • +
  • -

#6 roubzy  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 01-October 12

Re: Floyd's algorithm

Posted 28 October 2012 - 12:19 AM

ahh i know what is the problem. there is nothing wrong with your code you are 100% correct, but you are forgetting 1 thing, arrays start counting at zero. you teacher probably used 3 because he was counting from 1 to 4, but arrays count from 0 to 3, so all you got to do is just add +1.

so

path[i][j] = k;

should be

path[i][j] = k + 1;

hope this helps
Was This Post Helpful? 0
  • +
  • -

#7 bcnafegar  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 31
  • Joined: 13-May 11

Re: Floyd's algorithm

Posted 28 October 2012 - 01:07 PM

that makes sense, appreciate your help
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1