Алгоритм Дейкстры на куче. Найти кратчайшие пути до всех узлов от заданного узла - C#

Узнай цену своей работы

Формулировка задачи:

Уже больше суток бьюсь над формулированием запроса в гугл, чтобы он мне выдал какой-нибудь мануал по реализации алгоритма Дейкстры на d-куче. Нужно найти кратчайшие пути до всех узлов от заданного узла. Сам алгоритм Дейкстры уже реализовал. Что такое d-кучи понимаю и могу реализовать без проблем. А вот связать все вместе или найти как это сделать не могу уже долго. Сдавать через 7 часов. Помогите раскурить, пожалуйста
бамп. Никто не знает, чтоли? нашел только сомнительный код на плюсах
Листинг программы
  1. const int inf = 1e9;
  2. class edge
  3. {
  4. public :
  5. int v, w;
  6. edge (int _v, int _w) : v (_v), w (_w) {};
  7. };
  8. bool operator < (edge a, edge b) { return a.w < b.w || (a.w == b.w && a.v < b.v); }
  9. bool operator == (edge a, edge b) { return a.w == b.w && a.v == b.v; }
  10. void dij_sparse (int x, vector < vector < edge > > &e, vector < int > &w, vector < int > &p)
  11. {
  12. int i, j;
  13. int n = e.size ();
  14. vector < int > a (n, 0);
  15. w.assign (n, inf);
  16. p.assign (n, - 1);
  17. w[x] = 0;
  18. set < edge > u;
  19. for (i = 0; i < n; ++ i)
  20. u.insert (edge (i, i == x ? 0 : inf));
  21. for (i = 0; i < n; ++ i)
  22. {
  23. int v = (* u.begin ()).v;
  24. u.erase (u.begin ());
  25. a[v] = 1;
  26. for (j = 0; j < e[v].size (); ++ j)
  27. {
  28. int to = e[v][j].v;
  29. if (!a[to] && w[to] > w[v] + e[v][j].w)
  30. {
  31. u.erase (u.find (edge (to, w[to])));
  32. w[to] = w[v] + e[v][j].w;
  33. p[to] = v;
  34. u.insert (edge (to, w[to]));
  35. }
  36. }
  37. }
  38. }
Взято с http://hardfire.ru/Dij_sparse

Решение задачи: «Алгоритм Дейкстры на куче. Найти кратчайшие пути до всех узлов от заданного узла»

textual
Листинг программы
  1.             for (int i = 0; i < costs.Length; i++)
  2.             {
  3.                 Console.WriteLine("Пункт {0}, стоимость пути = {1}", names[i], costs[i]);
  4.             }

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

15   голосов , оценка 4.333 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы