# Floyd's algorithm

Page 1 of 1

## 6 Replies - 2109 Views - Last Post: 28 October 2012 - 01:07 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=297388&amp;s=d1c91ec23f18741188f06a962f5c9294&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 bcnafegar

• New D.I.C Head

Reputation: 0
• 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

• Saucy!

Reputation: 6208
• Posts: 23,953
• 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

• New D.I.C Head

Reputation: 0
• 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

Reputation: 4648
• Posts: 14,579
• 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

• New D.I.C Head

Reputation: 0
• 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

• New D.I.C Head

Reputation: 0
• 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

• New D.I.C Head

Reputation: 0
• 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

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }