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 ?

2
Contributors
2
Replies
3
Views
8 Years
Discussion Span
Last Post by 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.

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!!!

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.