Najmanje naporna staza

Dajkstrin algoritam

Zadatak se može rešiti jednostavnom modifikacijom Dajkstrinog algoritma za pronalaženje najkraćeg puta od gornjeg levog polja, pa do svih ostalih polja, uključujući i poslednje, donje desno polje. Jedina razlika u odnosu na uobičajeni Dajkstrin algoritam se u slučaju da je poznato najmajnje rastojanje $r_{uv}$ od čvora $u$ do čvora $v$ (najveća razlika visina na najboljem putu od $u$ do $v$ ) i rastojanje $r_{vw}$ od čvora $v$ do njemu susednog čvora $w$ (razlika visina), tada je najmanje rastojanje od čvora $u$ do čvora $v$ jednako $\max(r_{uv}, r_{vw})$ . Tada se vrednost rastojanja ažurira na osnovu dodele $r_{uw} := \min(r_{uw}, \max(r_{uv}, r_{vw}))$ .

“Težina” grane $(u, v)$ je u ovom primeru definisana kao razlika visina dva čvora koje ta grana spaja. “Dužina” puta $(v_0, v_1, \ldots, v_k)$ je ovde definisana kao maksimalna razlika visina čvorova na putu. “Zbir” dužine dva puta jednak je njihovom maksimumu. Ova metrika zadovoljava sledeća svojstva:

Nenegativnost: težina svake grane je nenegativna (jer se gleda apsolutna razlika visina).
Usmerenost: “dužina” puta koji se sastoji od jedne usmerene grane jednaka je “težini” te grane (što direktno sledi iz definicija).
Nejednakost trougla: Za svaka tri čvora $u$ , $v$ , $w$ , “dužina” najkraćeg puta od $u$ do $w$ je manja ili jednaka “zbiru” “dužine” najkraćeg puta od $u$ do $v$ i “težine” grane $v$ do $w$ . Zaista, “dužina” puta od $u$ do $w$ preko čvora $v$ je maksimum najveće razlike visina na putu od $u$ do $v$ i razlike visina čvorova $v$ i $w$ . Nemoguće je da je najmanja moguća razlika visina na putu od $u$ do $w$ veća od ovog broja (jer uvek možemo proći putem preko $v$ ).

Može se dokazati da su ova svojstva dovoljna da osiguraju korektnost Dajkstrinog algoritma.

Prikaži kompletan kôd

int najmanjeNapornaStaza(const vector<vector<int>>& visine) {
  // dimenzije matrice
  int m = visine.size(), n = visine[0].size();
  // rastojanje od početnog do svakog drugog čvora pamtimo u matrici 
  vector<vector<int>> rastojanje(m, vector<int>(n, INF));
  // podatak da li je do čvora određeno rastojanje pamtimo u matrici
  vector<vector<bool>> resen(m, vector<bool>(n, false));
  // red sa prioritetom koji koji sadrži trojke na čijem je prvom mestu
  // dužina grane, a zatim čvor iz kog ta grana polazi
  // (njegove koordinate)
  priority_queue<tuple<int, int, int>,
                 vector<tuple<int, int, int>>,
                 greater<tuple<int, int, int>>> pq;
  // rastojanje do početnog čvora je 0
  rastojanje[0][0] = 0;

  // krećemo od početnog čvora
  pq.emplace(0, 0, 0);
  while (!pq.empty()) {
    // skidamo element sa vrha reda sa prioritetom
    auto [tezina, v, k] = pq.top();
    pq.pop();
    // ako je do čvora na poziciji (v, k) ranije određen najkraći put,
    // taj čvor preskačemo
    if (resen[v][k])
      continue;
    // pamtimo da smo upravo odredili najkraći put do čvora na
    // poziciji (v, k)
    resen[v][k] = true;

    // prolazimo kroz sve susede ovog čvora
    int dv[] = {-1, 1, 0, 0};
    int dk[] = {0, 0, -1, 1};
    for (int i = 0; i < 4; i++) {
      int vv = v + dv[i];
      int kk = k + dk[i];
      if (!(0 <= vv && vv < m && 0 <= kk && kk < n))
        continue;

      // do kojih je najkraće rastonja još nepoznato
      if (resen[vv][kk])
        continue;

      // težina grane od trenutnog do susednog čvora
      int razlika = abs(visine[vv][kk] - visine[v][k]);
      // ažuriramo rastojanje do suseda ako je manje od dosadašnjeg
      int novoRastojanje = max(rastojanje[v][k], razlika);
      if (novoRastojanje < rastojanje[vv][kk]) {
        rastojanje[vv][kk] = novoRastojanje;
        pq.emplace(rastojanje[vv][kk], vv, kk);
      }
    }
  }
  // vraćamo najkraće rastojanje do ciljnog polja
  return rastojanje[m-1][n-1];
}

Najmanje naporna staza - Rešenje

Dajkstrin algoritam