Jose Manuel Heredia Hidalgo

Greenhorn

Posts: 1

posted 10 years ago

Hi there!

I'm witing because i've been working on a project, in this project The user has to give the initial city an the final. I've read about the Floyd's Algorithm. In my project i just have to use the final step of Floyd's Algorithm that is to check the final adjacency matrix, given by me.

This is the graph used

I would really appreciate any help!!!

Thanks

J. Manuel

I'm witing because i've been working on a project, in this project The user has to give the initial city an the final. I've read about the Floyd's Algorithm. In my project i just have to use the final step of Floyd's Algorithm that is to check the final adjacency matrix, given by me.

This is the graph used

I would really appreciate any help!!!

Thanks

J. Manuel

Craig Wood

Ranch Hand

Posts: 1535

posted 10 years ago

First things first. An adjacency matrix for your image of five nodes would have five rows

and five columns. The value for each cell is taken from the image/graph values.

There may be several ways to go about this such as using a large number/infinity in the

adjacency matrix for one-way direction/no connection or using a separate matrix with

binary or boolean values.

If we use the large number approach, then moving from node 3 to node 5 gives a matrix cell

value of 15; moving from node 5 to node 3 calls for a cell value of a large number

(infinity, not possible in the workings of Floyd's algorithm which tests for minimums).

With this approach, to check for a direct route between two nodes we look for a cell value

that is not zero (start node == end node) or infinity/large.

If you want to find the route of lowest/minimum value we need to consider every possible

path between the two nodes. This includes the direct node-to-node path just mentioned and

then all paths with one intermediary step between start and end. Then all possible paths

of two intermediary steps between start and end nodes. And for paths of increasing

intermediary steps up to the limit of numberOfNodes minus the start and stop node

selections; for your image: 5 - 2 = 3.

Then for each possible path, add up the values along the path segments obtained from the

adjacency matrix and save the lowest total along with the corresponding path.

*i just have to use the final step of Floyd's Algorithm that is to check the final*

adjacency matrix, given by me

adjacency matrix, given by me

First things first. An adjacency matrix for your image of five nodes would have five rows

and five columns. The value for each cell is taken from the image/graph values.

There may be several ways to go about this such as using a large number/infinity in the

adjacency matrix for one-way direction/no connection or using a separate matrix with

binary or boolean values.

If we use the large number approach, then moving from node 3 to node 5 gives a matrix cell

value of 15; moving from node 5 to node 3 calls for a cell value of a large number

(infinity, not possible in the workings of Floyd's algorithm which tests for minimums).

With this approach, to check for a direct route between two nodes we look for a cell value

that is not zero (start node == end node) or infinity/large.

If you want to find the route of lowest/minimum value we need to consider every possible

path between the two nodes. This includes the direct node-to-node path just mentioned and

then all paths with one intermediary step between start and end. Then all possible paths

of two intermediary steps between start and end nodes. And for paths of increasing

intermediary steps up to the limit of numberOfNodes minus the start and stop node

selections; for your image: 5 - 2 = 3.

Then for each possible path, add up the values along the path segments obtained from the

adjacency matrix and save the lowest total along with the corresponding path.