I've got a problem with applying a Bellman-Ford algorithm to 2D Array (not to graph)Input array has m x n dimensions:           s[1,1] s[1,2] ... s[1,n] -> Exit           s[2,1] s[2,2] ... s[2,n]           ... Entry ->  s[m,1] s[m,2] ... s[m,n]And it is room-alike (each entry is a room with s[x,y] cost of enterance). Each room could has also negative cost, and we have to find cheapest path from Entry to choosen room and to Exit.For example, we've got this array of rooms and costs:1   5   62  -3   45   2  -8And we want to walk over room [3,2], s[3,2] = 4. We are starting form 5 at [1,3] and must walk over [3,2] before we go to [3,3].And my question is, what is the best way to implement it in Bellman-Ford algorithm? I know that Dijkstry algorithm will not work becouse of negative cost.Is for each room from [0, maxHeight] and relax all neighbors correct? Like this:   for (int i = height-1; i >= 0; --i) {        for (int j = 0; j < width; ++j) {            int x = i;            int y = j;            if (x > 0) // up                Relax(x, y, x - 1, y);            if (y + 1 < width) // right                Relax(x, y, x, y + 1);            if (y > 0) // left                Relax(x, y, x, y - 1);            if (x + 1 < height) // down                Relax(x, y, x + 1, y);        }    }But how can I then read a cost to choosen room and from room to exit?
Belman-Ford 2d array variation problem
algorithms;graph;algorithm analysis;graph traversal