Shortest Path

[NT.]

Hi,

I am thinking about something that I heard in a discussion and I am not sure whether it is really like that or not. Calculating a shortest path on a graph can be done either using dijkstra's algorithm , basically DFS or by BFS. There might be some other ways as well. I was told that it is possible to use matrix multiplication storing edges weight in 1 matrix and nodes in the other and final product gives you shortest distance. I am not sure this is what it meant. I mean I have never heard that before. what do you guys think ?

[sneaker]

When you want to find shortest path between all pairs of corners you can use matrix multiplication where the result is a matrix D = dij where dij is the shortest path from corner vi to corner vj.

[NT.]

When you want to find shortest path between all pairs of corners you can use matrix multiplication where the result is a matrix D = dij where dij is the shortest path from corner vi to corner vj.

Thanks for the explanation!!!