Algorytm Dijkstry – układanie elementów przez kolejkę priorytetową

Cześć,
mam problem z implementacją algorytmu Dijkstry w języku C++. Z moich obserwacji wynika, że problemem jest sposób w jaki kolejka priorytetowa układa elementy, ale być może się mylę. Widziałem różne implementacje w internecie, ale wszystkie były dla mnie mało zrozumiałe i stosowały klasy lub struktury, które jeszcze niezbyt ogarniam. Chciałbym, żeby w miarę możliwości kod był jak najprostszy, gdyż będę musiał umieć go napisać z pamięci na olimpiadzie.
Jeśli ktoś mógłby mi pomóc byłbym bardzo wdzięczny
Pozdrawiam serdecznie ;)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <utility>
#include <functional>

using namespace std;

int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
	vector <int> *l = new vector <int>[n + 1];
	int **w = new int*[n + 1];
	for (int i = 1; i <= n; i++){
		w[i] = new int[n + 1];
	}
	for (int i = 0; i < m; i++){
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		l[a].push_back(b);
		l[b].push_back(a);
		w[a][b] = c;
	}
	int s, k;
	scanf("%d %d", &s, &k);
	int *d = new int[n + 1];
	for (int i = 0; i <= n; i++) {
		d[i] = INT_MAX;
	}
	d[s] = 0;
	priority_queue <pair<int*, int>> q;
	for (int i = 1; i <= n; i++) {
		q.push(make_pair(&d[i], i));
	}
	int u;
	while (!q.empty()) {
		u = q.top().second;
		q.pop();
		for (int i = 0; i < l[u].size(); i++)
		{
			d[l[u][i]] = min(d[l[u][i]], d[u] + w[u][l[u][i]]);
		}
	}
	printf("%d", d[k]);



	cin.get();
	cin.get();
}

Co do samego kodu:

gdyż będę musiał umieć go napisać z pamięci na olimpiadzie.

Naprawdę? To chyba najniebezpieczniejsze, na co mogłeś wpaść. Zapomnisz jednej linijki i zgłupiejesz, spanikujesz i nie napiszesz nic. Postaraj się zrozumieć swój kod, nie będziesz musiał pisać go z pamięci.

vector <int> *l = new vector <int>[n + 1];

To nie wygląda dobrze... jeśli potrzebujesz dynamicznej tablicy dwuwymiarowej zrób vector vectorów:

vector< vector<int> > matrix;

Nazewnictwo zmiennych!! Pisząc coś takiego:

d[l[u][i]] = min(d[l[u][i]], d[u] + w[u][l[u][i]]);

możesz sam dostać oczopląsu, do tego nigdy nie zrozumiesz potem własnego kodu, a to znacznie utrudni Ci jego ewentualne zapamiętanie (co stanowczo odradzam, jak mówiłem wcześniej). Nazywaj zmienne tym, czym rzeczywiście są -> zmienna przechowuje liczbę kroków? Nazwij ją stepCount

gdyż będę musiał umieć go napisać z pamięci na olimpiadzie.

I wielkie zdziwienie, dlaczego twierdzę, że Olimpiady programistyczne ssą.

Okej, może źle to ująłem. Mówiąc "z pamięci" miałem bardziej na myśli, że będę umiał go napisać, bo np tych implementacji z neta nie ogarniam i za nic bym nie umiał ich napisać. W każdym razie dzięki wielkie za odpowiedzi, postaram się zastosować do waszych rad. ;)

Szymon Bagiński napisał(a):

  	d[l[u][i]] = min(d[l[u][i]], d[u] + w[u][l[u][i]]);

Programuję w C/C++ już jakąś dekadę, a nigdy w życiu, nawet przy specjalnie pisanych w poryty sposób programach nie przyszło mi do głowy że da się
stworzyć coś takiego jak

d[l[u][i]]

4programmers bawi i uczy

Wracając jednak do wątku głównego:

że problemem jest sposób w jaki kolejka priorytetowa układa elementy, ale być może się mylę.

Jaki dokładnie jest problem z ułożeniem elementów? Czego oczekujesz a co otrzymujesz?

Generalnie chciałbym żeby kolejka sortowała według wartości zmiennych tablicy d, ale że musi mieć dostęp do wartości na bieżąco to w parze wpisałem jako pierwszy typ wskaźnik do int. Nie wiem czy poszedłem przez to w dobrą stronę ale to jedyne co udało mi się wykombinować

No generalnie, kiepski pomysł, w tym momencie sortujesz po kolejności w tablicy. (bo &d[1] - &d[0] == sizeof(int), niezależnie od zawartości tablicy).

Poza tym, użycie kolejki priorytetowej w tym zadaniu nie pomoże, gdyż na Olimpiadzie grafy są zazwyczaj gęste, więc w takiej wersji, O(|V|^2) = O(|E|) (rzuć okiem na https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Running_time )

Oto moja implementacja sprzed dwóch lat:

#include <iostream>
#include <vector>
#include <list>
#include <cstdint>

const uint64_t infinity = (1<<30)-1<<1;

using std::vector;
using std::cin;
using std::cout;
using edge = std::pair<int, uint64_t>;
using graph = vector<std::list<edge>>;

int infimum(vector<uint64_t>& v, vector<bool>& vis) {
  int m = 0;
  uint64_t a = infinity;
  for (uint64_t i = 0; i < v.size(); ++i) {
    if (!vis[i] and v[i] < a) {
      m = i;
      a = v[i];
    }
  }
  if (m == 0 and a == infinity) {
      return -1;
  }
  return m;
}

void print(int e) {
  cout << e;
}

template<typename A, typename B>
void print(std::pair<A, B> p) {
    print(p.first);
    cout << " ";
    print(p.second);
}

template<typename T>
void print(std::list<T>& l) {
  for (auto e: l) {
    print(e);
    cout << " ";
  }  cout << "\n";

}

template<typename T>
void print(vector<T>& v) {
  for (auto e: v) {
    print(e);
    cout << " ";//
  }
  cout << "\n";
}

void dijkstra(graph& g, vector<uint64_t>& cost, vector<int>& parent,
              vector<bool>& visited, int v) {
  if (visited[v]) {
    return;
  }
  visited[v] = true;
  for (auto u: g[v]) {
    if (u.second + cost[v] < cost[u.first]) {
      cost[u.first] = u.second + cost[v];
      parent[u.first] = v;
    }
  }
  int m = infimum(cost, visited);
  if (m == -1) {
      return;
  }
  dijkstra(g, cost, parent, visited, m);
}

int main() {
  int m, n, s;
  cin >> n >> m >> s;
  graph g(n);
  for (int i = 0; i < m; ++i) {
    int a ,b, c;
    cin >> a >> b >> c;
    g[a].push_back(std::make_pair(b, c));
    g[b].push_back(std::make_pair(a, c));
  }

  vector<uint64_t> cost(n, infinity);
  vector<int> parent(n, -1);
  vector<bool> visited(n, false);
  cost[s] = 0;
  parent[s] = s;
  dijkstra(g, cost, parent, visited, s);

  print(cost);
  print(parent);

}

Dzięki wielkie, ogarnę sobie w wolnej chwili