0

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.
0

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.

0

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.