Дижкстра

За энэ удаагийхаа постоор Дижкстрагийн алгоритмыг тайлбарлая. Бидэнд дараах бодлого өгөгдсөн байг.

N оройтой M ирмэгтэй, жинтэй, чиглэлт граф өгөгдсөн бол А хотоос Б хүртлэх хамгийн богино замын маршрутыг хэвлэ.

Дижкстрагийн алгоритм нь үнэндээ А хотоос ганцхан Б хот хүртлэх биш, А хотоос бүх хот хүртлэх богино замуудыг олдог. Мөн графыг чиглэлтэй мөн чиглэлгүй ч байхад бодолт хүчинтэй байдаг. Харин ганц тавьдаг шаардлага бол граф-д сөрөг утгатай жин байхыг зөвшөөрдөггүй. Сөрөг жинтэй графын хувьд Bellman Ford-н алгоритм авч үзнэ(дараа).
Алгоритм бол маш амархан, яг л түвшний нэвтрэлт шиг ажиллана (Түвшний нэвтрэлтээ сайн ойлгоогүй бол ЭНЭ постыг сайн уншаарай) , энгийн дараах Greedy санаан дээр тулгуурладаг.

Бид ямар нэгэн С орой хүртлэх богино замыг олцон гэж үзье. Мэдээж А оройгоос С орой хүртэл хэрэглэгдэж байгаа оройнуудыг дахин ашиглахгүй. Тэгвэл С оройгоос хамгийн ойрхон орших хөрш оройг нь сонгоно. Энэ оройг D гэж үзье. Энэ D маань А оройгоос D орой хүртлэх богино замыг олчихлоо гэсэн үг. Алгоритм ердөө л энэ. Маш амархан энгийн байгаа биз. Харин програм ямар үед зогсох вэ? Б орой дээр ирсэн үед эсвэл бүх орой дээр очсон үед зогсоно.
Харин код бичих, тохирсон өгөгдөлийн бүтцийг сонгосноор Дижкстраг маш хүчтэй болгож байдаг юм.

Бид түвшний нэвтрэлт хийхдээ дараалалдаа бүх хөрш оройнуудыг хийгээд явдаг. Үүнтэй яг л адилхан бид дараалалдаа хөрш оройнуудыг хийгээд, хамгийн ойрхон оройг нь дарааллаасаа хасаад явах юм. Сүүлд хасагдсан оройн бүх хөрш оройнуудыг дараалалдаа нэмээд, дарааллаас хамгийн бага жинг сонгоно гэсэн үг. Энд нэг зүйлийг нэмж тайлбарлахад ямар нэгэн орой хүртлэх богино зайг олсны дараа, дараагийн хамгийн бага оройг сонгоно гэдэг маань, тухайн сүүлд ирсэн оройн хамгийн ойрхон хөрш оройг олох биш, дараалалд хадгалагдаж байгаа бүх оройнуудаас хамгийн багыг олох ёстой шүү!!
Алгоритм ойлгомжтой байх, одоо анализ хийгээд, шаардлагатай өгөгдлийн бүтцээ үзье (Энэ хүртэл маш сайн ойгоцон байх ёстой шүү).

Алгоритмаас харахад алхам бүрдээ дараалалд байгаа жингүүдээс хамгийн багыг нь сонгоод яваад байх нь. Дарааллаа энгийн массиваар шийдэх гээд үзье. Хамгийн бага жинг шугаман хайлтаар хийвэл O(M). Олсон элементээ устгах нь мөн л O(M). Ингэвэл манай алгоритм O(NM) болохнээ. Бид түвшний нэвтрэлт дээр ашигласан QUEUE өгөгдөлийн бүтцийг хэрэглэх боломжгүй. Одоо арай өөр өгөгдлийн бүтэц авч үзье.

PRIORITY_QUEUE

Энэ өгөгдөлийн бүтцийн хийдэг үйлдэлүүд QUEUE өгөгдөлийн бүтэцтэй яг адилхан. Харин дараахь онцлогтой.

1. Хамгийн бага элементийг/их элементийг O(1);

2. Хамгийн бага/их элементийг устгах O(LogM);

3. Элемент нэмэх O(LogM).

Одоо бид алгоритмаа O(NLogM)-д шийдэх бүрэн боломжтой боллоо. Яг үнэн хэрэгтээ бол Дижкстрагийн алгоритмыг Heap өгөгдөлийн бүтэц ашигладаг ба хугацааны үнэлгээ O(NLogM) байдаг. Priority_Queue өгөгдлийн бүтэц Heap-тэй бараг адилхан бүтэц төрөл юм. Удахгүй Heap-н талаар пост оруулна. Одоо Java болон C++ дээрх кодыг сонирхуулъя.

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <stack>
#include <queue>
#include <vector>
#include <cstdio>
#include <string>
#include <bitset>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <sstream>
#include <iostream>
#include <algorithm>
#define sqr(x) ((x)*(x))
#define ABS(x) ((x<0)?(-(x)):(x))
#define eps (1e-9)
#define mp make_pair
#define pb push_back
#define Pair pair<int,int> //V W
#define xx first
#define yy second
#define equal(a,b) (ABS(a-b)<eps)
using namespace std;

template<class T> string tostring(T x) { ostringstream out; out<<x; return out.str();}
long long toint(string s) { istringstream in(s); long long x; in>>x; return x; }
#define Max 100010
/////////////////////////////////////////////////////////////////////////////////////////////////////
struct cmp{
   bool operator()(const Pair &a, const Pair &b)const{
       return a.yy>b.yy;
   }
};
const long long INF = 12345678987654321LL;
priority_queue< Pair, vector< Pair >, cmp>q;
vector< Pair >v[Max];
int n, m;
bool used[Max];
int uu[Max];
long long d[Max];
void dfs(int i){
    if(i==0){printf("1 ");return;}
    dfs(uu[i]);
    printf("%d ", i+1);
}
int main(int argc, char *argv[]) {
   //freopen("dij.in", "r", stdin);
   //freopen("dij.out", "w", stdout);
   scanf("%d%d", &n, &m);
   while(m--){
      int a, b, w;
      scanf("%d%d%d", &a, &b, &w);
      a--;
      --b;
      v[a].pb(mp(b, w));
      v[b].pb(mp(a, w));
   }
   uu[0] = 0;
   for(int i=0; i<n; i++)d[i] = INF;
   d[0] = 0;
   q.push(mp(0, 0));
   while(q.size()){
      int u = q.top().xx;
      q.pop();
      int sz = v[u].size();
      for(int i=0; i<sz; i++){
          int vv = v[u][i].xx;
          int ww = v[u][i].yy;
          if(!used[vv]&&d[u]+ww<d[vv]){
             d[vv] = d[u] + ww;
             q.push(mp(vv, d[vv]));
             uu[vv] = u;
          } 
      }
      used[u] = 1;
   }
   if(d[n-1]==INF)printf("-1\n");
   else
   dfs(n-1);
return 0;
}

import java.io.*;
import java.util.*;

public class test2
{

 public static void main(String[] args)
 {
  new test2().run();
 }

 PrintWriter out = null;

 void run()
 {
  Scanner in = new Scanner(System.in);
  out = new PrintWriter(System.out);

  int n = in.nextInt();
  int m = in.nextInt();

  ArrayList<Ele>[] mat = new ArrayList[n];
  for (int i = 0; i < n; i++)
   mat[i] = new ArrayList<Ele>();

  for (int i = 0; i < m; i++)
  {
   int a = in.nextInt() - 1;
   int b = in.nextInt() - 1;
   int c = in.nextInt();

   mat[a].add(new Ele(b, c));
   mat[b].add(new Ele(a, c));
  }

  boolean[] visited = new boolean[n];
  int[] prev = new int[n];
  int[] costs = new int[n];
  Arrays.fill(costs, Integer.MAX_VALUE);
  costs[0] = 0;

  prev[0] = -1;

  PriorityQueue<Vert> pq = new PriorityQueue<Vert>();
  ArrayList<Integer> al = new ArrayList<Integer>();

  pq.add(new Vert(0, 0));

  while (!pq.isEmpty())
  {
   Vert v = pq.poll();

   if (v.id == n - 1)
   {
    int k = n - 1;
    while (k >= 0)
    {
     al.add(k);
     k = prev[k];
    }
    break;
   }
   if (visited[v.id])
    continue;

   visited[v.id] = true;

   int i = v.id;
   for (Ele e : mat[i])
   {
    int j = e.y;
    int d = e.d;

    if (!visited[j] && d + v.cost < costs[j])
    {
     costs[j] = d + v.cost;
     prev[j] = i;

     pq.add(new Vert(j, costs[j]));
    }
   }
  }

  if (al.size() < 2 || al.get(al.size() - 1) != 0)
   out.println(-1);
  else
  {
   for (int i = al.size() - 1; i >= 0; i--)
    out.print((al.get(i) + 1) + " ");
  }
  out.close();
 }
}

class Ele
{
 int y;
 int d;

 public Ele(int _y, int _d)
 {
  y = _y;
  d = _d;
 }
}

class Vert implements Comparable<Vert>
{
 int id;
 int cost;

 public Vert(int _i, int _c)
 {
  id = _i;
  cost = _c;
 }

 public int compareTo(Vert o)
 {
  return cost - o.cost;
 }
}