Bellman-Ford 2d problema di variazione dell'array

Ho riscontrato un problema con l'applicazione di un algoritmo Bellman-Ford alla matrice 2D (non al grafico)

L'array di input ha dimensioni m x n :

           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]

Ed è uguale alla stanza (ogni entrata è una stanza con s [x, y] costo di ingresso ). Ogni stanza potrebbe avere anche costo negativo e dobbiamo trovare il percorso più economico tra Entrata nella stanza scelta ed Esci .

Ad esempio, abbiamo questa gamma di stanze e costi:

1   5   6
2  -3   4
5   2  -8

E vogliamo camminare sopra la stanza [3,2] , s [3,2] = 4. Stiamo iniziando la forma 5 su [1,3] e vai sopra [3,2] prima di andare a [3,3] .

E la mia domanda è: qual è il modo migliore per implementarlo nell'algoritmo di Bellman-Ford? So che l'algoritmo di Dijkstry non funzionerà a causa del costo negativo.

È per ogni stanza da [0, maxHeight] e si rilassano tutti i vicini corretti? In questo modo:

   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);
        }
    }

Ma come posso leggere un costo per la stanza scelta e dalla stanza per uscire?