Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have to use Warshall's algorithm to find the shortest paths and their minimal weights between all pairs of nodes in the following weighted graph.

http://prntscr.com/pgix8

From what I've been suggested I have to compute some matrices but I don't have a clear idea of what I am supposed to do.

I know how to compute $n * n$ matrix $P^{(n)}$ matrix of paths between nodes, do I have to compute until $P^{(5)}$ and if so, what does that mean? Moreover, I have to compute the minimal weights, how do I do that?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

See Floyd-Warshall algorithm here. The matrix is a two-dimensional array $N*N$ where $N$ represents the number of nodes in your graph. When you access your matrix, you provide the start node and the end node and it gets populated with values representing the corresponding distance. In other words if I write: dist[0][1], then I'm writing or reading the distance from node 0 to node 1. Needless to say, if going from node 0 to node 1 is the same thing as going from node 1 to node 0, your matrix is only really going to need half, since you're not going to need to evaluate the distance from node 1 to node 0.

Hope that helps. Happy coding.

share|improve this answer
    
I have to do it by hand, thanks for the suggestion though.. –  Dream Box Jan 17 '13 at 15:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.