Sign up ×

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?

share|improve this question
Have you tried using any approach to solve this problem? Giving some info on how you've attacked it would help greatly. – itdoesntwork Aug 6 '12 at 21:06
Is the direct journey between a & b not the minimum? – Dan W Aug 6 '12 at 21:07
A typical (and easy) solution would involve an A* search... which is based on a waypoint graph. So, why are you restricting yourself to matrix calculations? – Sebastian Aug 6 '12 at 21:08
Yeah definitely!...In the matrix A I looked up the column number b and looked for the least value. Suppose this least value occurs in row number x, then I went to column X and followed suit. The above two steps are continued until the sum of all the values exceeds A[a][b]. If the sum exceeds, then A[a][b] is returned else if the initial destination (i.e. A) is reached before sum exceeds A[a][b], this sum is returned. The approach is obviously flawed. – jigsawmnc Aug 6 '12 at 21:12
1‌​ights Not sure why you wouldn't want to use graph-theory, as you are dealing a graph- just because you're storing it as an adjacency matrix rather than using nodes/pointers doesn't change the fact that it's a graph... – BlueRaja - Danny Pflughoeft Aug 6 '12 at 21:36

2 Answers 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...)

share|improve this answer
Will Djikstra's Algorithm work even if A[i][j] is not necessarily equal to A[j][i]? – jigsawmnc Aug 6 '12 at 21:19
It's not immediately clear to me how A[i][j] != A[j][i] would affect the correctness of Dijkstra's algorithm. – Dennis Meng Aug 6 '12 at 21:25
@jigsawmnc: Yes, Djikstra's will work on weighted directed graphs – BlueRaja - Danny Pflughoeft Aug 6 '12 at 21:34

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

Wiki link to TSP

share|improve this answer
The TSP has the requirements that you MUST visit each city EXACTLY 1 time in the shortest amount of time. This problem is about finding the shortest distance between 2 cities given the times between all of them. – Dan W Aug 6 '12 at 21:14

Your Answer


