Member Avatar for 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 ?

  • 2 Contributors
  • 2 Replies
  • 103 Views
  • 21 Hours Discussion Span
  • Latest Post Latest Post by NT.
Member Avatar for 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.

Member Avatar for 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!!!

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.