Dijkstra pe matrice

Am învățat algoritmul lui Lee - găsește drumul cel mai scurt pe o matrice unde toate celulele costă la fel (fiecare pas = distanța crește cu 1).

Dar dacă celulele au costuri diferite? De exemplu: - Un labirint unde unele zone sunt mai greu de traversat (nisip, apă) - O hartă unde fiecare teren are un cost propriu - O rețea unde unele zone consumă mai multă energie

Pentru asta folosim Dijkstra pe matrice - o generalizare a lui Lee care ține cont de costuri.

Problema

Avem o matrice n x m unde fiecare celulă a[i][j] are un cost (un număr pozitiv). Vrem să găsim drumul de cost minim de la (sx, sy) la (fx, fy).

La fiecare pas, ne deplasăm într-o celulă vecină (sus, jos, stânga, dreapta) și plătim costul acelei celule.

Exemplu

Matrice de costuri:
1 3 1 1 5
1 1 5 1 1
4 2 1 1 5
1 1 1 5 1

Start (1,1), Final (4,5)

Drum optim: mergem pe celulele cu cost mic
Cost total = suma costurilor celulelor vizitate

De ce NU merge Lee?

Lee folosește o coadă obișnuită (FIFO) - explorează în ordinea descoperirii, care corespunde distanței în pași (1, 2, 3…).

Cu costuri diferite, celula explorată prima nu e neapărat cea cu cost minim. Trebuie să explorăm mereu celula cu costul minim acumulat.

Soluția: coadă de priorități (min-heap) în loc de coadă obișnuită.

Algoritmul Dijkstra pe matrice

Inițializăm dist[i][j] = infinit pentru toate celulele.
dist[sx][sy] = a[sx][sy] (costul celulei de start).
Punem (dist[sx][sy], sx, sy) în priority_queue (min-heap).
Cât timp coada nu e goală:
- Scoatem celula cu costul minim curent.
- Dacă am vizitat-o deja, o sărim.
- Pentru fiecare vecin, calculăm costul nou.
- Dacă e mai bun decât ce aveam, actualizăm și adăugăm în coadă.

Codul complet

#include <fstream>
#include <queue>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

const int INF = 1000000000;
int a[101][101];
int dist[101][101];
int n, m;

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

// (cost, x, y) - coada de prioritati (min-heap)
struct Nod {
    int cost, x, y;
    bool operator>(const Nod &alt) const {
        return cost > alt.cost;
    }
};

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            fin >> a[i][j];
            dist[i][j] = INF;
        }

    int sx, sy, fx, fy;
    fin >> sx >> sy >> fx >> fy;

    priority_queue<Nod, vector<Nod>, greater<Nod>> pq;

    dist[sx][sy] = a[sx][sy];
    pq.push({dist[sx][sy], sx, sy});

    while (!pq.empty()) {
        Nod nod = pq.top();
        pq.pop();

        int x = nod.x, y = nod.y, cost = nod.cost;

        // Daca am gasit deja un drum mai bun, sarim
        if (cost > dist[x][y]) continue;

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];

            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
                int costNou = cost + a[nx][ny];
                if (costNou < dist[nx][ny]) {
                    dist[nx][ny] = costNou;
                    pq.push({costNou, nx, ny});
                }
            }
        }
    }

    if (dist[fx][fy] == INF)
        fout << "Nu se poate ajunge";
    else
        fout << dist[fx][fy];

    return 0;
}

date.in:

date.out:

Explicație rezultat

Un drum posibil: (1,1) → (2,1) → (2,2) → (3,2) → (3,3) → (3,4) → (4,4)... sau altă combinație.

Costul minim e suma costurilor celulelor vizitate pe drumul optim.

Structura `Nod`

struct Nod {
    int cost, x, y;
    bool operator>(const Nod &alt) const {
        return cost > alt.cost;
    }
};

Am definit cum se compară două noduri - după cost. priority_queue cu greater<Nod> va ține mereu nodul cu costul minim în vârf.

Alternativă mai simplă: putem folosi pair<int, pair<int,int>> - primul element e costul, al doilea e poziția. Priority queue știe automat să compare perechi.

priority_queue<pair<int, pair<int,int>>,
vector<pair<int, pair<int,int>>>,
greater<pair<int, pair<int,int>>>> pq;

pq.push({cost, {x, y}});

De ce verificăm `cost > dist[x][y]`?

if (cost > dist[x][y]) continue;

Un nod poate fi adăugat în coadă de mai multe ori (de fiecare dată când găsim un drum mai bun). Când îl scoatem, verificăm dacă valoarea din coadă mai e actuală.

Dacă am găsit deja un drum mai bun către (x, y), ignorăm intrarea veche din coadă.

Fără această verificare, codul tot merge corect, dar e mai lent.

Dijkstra vs Lee

	Lee (BFS)	Dijkstra
Costuri egale?	DA (toate 1)	DA sau diferite
Structura	Coadă (FIFO)	Priority queue (min-heap)
Complexitate	O(n*m)	O(nm log(n*m))
Când folosim	Costuri uniforme	Costuri diferite

Regula: dacă toate celulele costă la fel, folosește Lee (mai rapid). Dacă nu, folosește Dijkstra.

Varianta cu cost pe muchii (nu pe celule)

Uneori costul nu e pe celulă, ci pe tranziție (mersul de la o celulă la alta):

int costTranzitie[101][101][4]; // pentru fiecare celulă, cost pe 4 direcții

// În Dijkstra:
int costNou = cost + costTranzitie[x][y][d];

Restul algoritmului rămâne identic.

Ziduri impenetrabile

Dacă matricea conține ziduri (celule în care nu putem intra), le marcăm cu un cost uriaș sau cu o valoare specială:

if (a[nx][ny] == -1) continue;  // -1 = zid, sărim peste

Sau declarăm INF pentru ziduri și verificăm înainte de intrare.

Reconstruirea drumului

Pentru a afla nu doar costul, ci și drumul efectiv, salvăm pentru fiecare celulă de unde am venit:

int parentX[101][101], parentY[101][101];

// Când actualizăm dist:
if (costNou < dist[nx][ny]) {
    dist[nx][ny] = costNou;
    parentX[nx][ny] = x;
    parentY[nx][ny] = y;
    pq.push({costNou, nx, ny});
}

// La final, reconstruim drumul de la (fx,fy) înapoi la (sx,sy):
int x = fx, y = fy;
while (x != sx || y != sy) {
    fout << "(" << x << "," << y << ") ";
    int px = parentX[x][y];
    int py = parentY[x][y];
    x = px;
    y = py;
}
fout << "(" << sx << "," << sy << ")";

Afișăm drumul de la final la start - îl putem inversa dacă vrem ordinea corectă.

Exemplu complet cu afișare drum

#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

const int INF = 1000000000;
int a[101][101];
int dist[101][101];
int parentX[101][101], parentY[101][101];
int n, m;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            fin >> a[i][j];
            dist[i][j] = INF;
        }

    int sx, sy, fx, fy;
    fin >> sx >> sy >> fx >> fy;

    priority_queue<pair<int, pair<int,int>>,
                   vector<pair<int, pair<int,int>>>,
                   greater<pair<int, pair<int,int>>>> pq;

    dist[sx][sy] = a[sx][sy];
    pq.push({dist[sx][sy], {sx, sy}});

    while (!pq.empty()) {
        int cost = pq.top().first;
        int x = pq.top().second.first;
        int y = pq.top().second.second;
        pq.pop();

        if (cost > dist[x][y]) continue;

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];

            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
                int costNou = cost + a[nx][ny];
                if (costNou < dist[nx][ny]) {
                    dist[nx][ny] = costNou;
                    parentX[nx][ny] = x;
                    parentY[nx][ny] = y;
                    pq.push({costNou, {nx, ny}});
                }
            }
        }
    }

    fout << "Cost minim: " << dist[fx][fy] << "\n";

    // Reconstruim drumul
    vector<pair<int,int>> drum;
    int x = fx, y = fy;
    while (x != sx || y != sy) {
        drum.push_back({x, y});
        int px = parentX[x][y];
        int py = parentY[x][y];
        x = px; y = py;
    }
    drum.push_back({sx, sy});

    fout << "Drum: ";
    for (int i = drum.size() - 1; i >= 0; i--)
        fout << "(" << drum[i].first << "," << drum[i].second << ") ";

    return 0;
}

Greșeli frecvente

1. Folosirea unei cozi obișnuite

queue<Nod> q; // GREȘIT - nu garantează ordinea după cost

La Dijkstra trebuie priority queue. Lee funcționează cu queue doar pentru că toate costurile sunt egale.

2. Costuri negative

Dijkstra NU funcționează cu costuri negative. Dacă ai costuri negative, folosește alt algoritm (Bellman-Ford).

3. Uitarea costului celulei de start

dist[sx][sy] = 0;              // GREȘIT dacă costul se plătește și pe start
dist[sx][sy] = a[sx][sy];      // CORECT dacă plătim costul celulei de start

Depinde de problemă - citește enunțul cu atenție.

4. Verificarea `cost > dist[x][y]`

// Fără verificare - mai lent, dar funcționează
// Cu verificare - optimizare importantă
if (cost > dist[x][y]) continue;

Fără ea, procesăm același nod de mai multe ori (de câte ori a fost adăugat în coadă).

Ce să reții

Dijkstra pe matrice = Lee cu costuri diferite pe celule.
Folosim priority queue (min-heap) în loc de coadă obișnuită.
dist[i][j] = costul minim de la start la (i,j).
La fiecare pas, scoatem nodul cu costul minim din coadă.
Complexitate: **O(nm log(n*m))**.
Nu funcționează cu costuri negative.
Pentru reconstruirea drumului, salvăm părintele fiecărei celule.