Алгоритм Дейкстры на куче. Найти кратчайшие пути до всех узлов от заданного узла - C#
Формулировка задачи:
Уже больше суток бьюсь над формулированием запроса в гугл, чтобы он мне выдал какой-нибудь мануал по реализации алгоритма Дейкстры на d-куче.
Нужно найти кратчайшие пути до всех узлов от заданного узла. Сам алгоритм Дейкстры уже реализовал. Что такое d-кучи понимаю и могу реализовать без проблем. А вот связать все вместе или найти как это сделать не могу уже долго. Сдавать через 7 часов. Помогите раскурить, пожалуйста
Взято с http://hardfire.ru/Dij_sparse
бамп. Никто не знает, чтоли?
нашел только сомнительный код на плюсах
const int inf = 1e9; class edge { public : int v, w; edge (int _v, int _w) : v (_v), w (_w) {}; }; bool operator < (edge a, edge b) { return a.w < b.w || (a.w == b.w && a.v < b.v); } bool operator == (edge a, edge b) { return a.w == b.w && a.v == b.v; } void dij_sparse (int x, vector < vector < edge > > &e, vector < int > &w, vector < int > &p) { int i, j; int n = e.size (); vector < int > a (n, 0); w.assign (n, inf); p.assign (n, - 1); w[x] = 0; set < edge > u; for (i = 0; i < n; ++ i) u.insert (edge (i, i == x ? 0 : inf)); for (i = 0; i < n; ++ i) { int v = (* u.begin ()).v; u.erase (u.begin ()); a[v] = 1; for (j = 0; j < e[v].size (); ++ j) { int to = e[v][j].v; if (!a[to] && w[to] > w[v] + e[v][j].w) { u.erase (u.find (edge (to, w[to]))); w[to] = w[v] + e[v][j].w; p[to] = v; u.insert (edge (to, w[to])); } } } }
Решение задачи: «Алгоритм Дейкстры на куче. Найти кратчайшие пути до всех узлов от заданного узла»
textual
Листинг программы
for (int i = 0; i < costs.Length; i++) { Console.WriteLine("Пункт {0}, стоимость пути = {1}", names[i], costs[i]); }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д