How to calculate minimum time of travel between two places when a matrix containing the time of travel between each node is given

Question

For n stations a n*n matrix A is given such that A[i][j] represents time of direct journey from station i to j (i,j <= n).

The person travelling between stations always seeks least time. Given two station numbers a, b, how to proceed about calculating minimum time of travel between them?

Can this problem be solved without using graph theory, i.e. just by matrix A alone?

Answer 1

This looks strikingly similar to the traveling salesman problem which is NP hard.

Wiki link to TSP

Answer 2

You do need graph theory in order to solve it - more specifically, you need Dijkstra's algorithm. Representing the graph as a matrix is neither an advantage nor a disadvantage to that algorithm.

Note, though, that Dijkstra's algorithm requires all distances to be nonnegative. If for some reason you have negative "distances" in your matrix, you must use the slower Bellman-Ford algorithm instead.

(If you're really keen on using matrix operations and don't mind that it will be terribly slow, you could use the Floyd-Warshall algorithm, which is based on quite simple matrix operations, to compute the shortest paths between all pairs of stations (massive overkill), and then pick the pair you're interested in...)