CODEWITHSUNDEEP
javascriptarraysalgorithmmultidimensional-arraydijkstra
KthProg
KthProg

Reputation: 2117

Dijkstra's algorithm on three dimensional array

I really cannot figure out how to implement this even in psuedo-code. The user enters in something like this:

[
  [
     [0,1]
  ],
  [
    [5,6],[7,8]
  ],
  [
    [91,17],[18,42]
  ],
  [
    [20,54]
  ]
]

Basically this is a path where [0,1] maps to ([5,6] and [7,8]) each of which maps to ([91,17] and [18,42]) and so on, the cost is the distance between the points. The starting point is [0, 1] and the ending point is [20,54]. There is always one starting point and one ending point, and all the points in the previous index map to the points in the next index.

How do I implement Dijkstra's algorithm for this kind of data structure?

This image may help (not to scale): enter image description here

Green is the start and red is the end.

Upvotes: 1

Views: 1200

Answers (1)

MrGreen
MrGreen

Reputation: 499

Notice that the given array is two dimensional if we considered the entry in the array as a pair (x, y).

The basic idea is build the graph, assign the cost of edges, and then apply the standard Dijkstra's algorithm.

Building the graph:

Make 2 hash tables H and Q where H([x,y]) maps a vertex (x,y) to a number between 0 and n - 1, and Q maps an integer between 0 and n - 1 to a vertex (x, y). n is the number of vertices in the graph. We can find n easily by looping over all the vertices in the given 2d array. Let's call the given array A

Pseudo-code of hashing: 

n = 0
for(i = 0; i < length of A ; i++)
    for(int j = 0; j < length of A[i]; j++)
            H[A[i][j]] = n
            Q[n] = A[i][j]
            n++

Notice that A[i][j] is actually a pair of integers, so the key of H should be a pair of integers.

Now we can build the graph considering vertices as numbers between 0 and n - 1. We can represent the graph as an adjacency list

Psudo-code of constructing the graph:

array g[n][]                              //-- adjacency list of the graph
for(int i = 0; i < length of A - 1; i++)  //-- notice the "-1"
    for(int j = 0; j < length of A[i]; j++)
        for(int k = 0; k < length of A[i + 1]; k++)
            g[ H[A[i][j]] ].insert (H[ A[i + 1][k] ])
            g[ H[ A[i + 1][k] ].insert( H[A[i][j]] )     //-- assuming the graph is undirected

By doing this, we have built the graph. Now we can apply the standard Dijkstra's algorithm on the graph g. To find the cost of an edge between two vertices u and v we can use the hash table Q in order to get the coordinates of u and v. Then the cost of the edge is the Euclidean distance between points Q[u] and Q[v].

Pseudo-code for cost of an edge between two vertices u and v 

cost(int u, int v)
    return Euclidean_distance(Q[u], Q[v])

Upvotes: 1

Related Questions