Kurt
Юзверь возвращаться будет?

Есть способы приближенного решения - алгоритм Прима например.

Цитата

Изначально все вершины кроме одной (корня) отмечаются как не входящие в дерево. Далее, на каждом шаге к существующему дереву добавляется ребро минимального веса (вместе с вершиной, к которой он ведет).

Цитата

В данном случае задача на плоскости приближенно решается с ошибкой не более чем в 2 раза

время на решение O(E*logV), (где E — мощность множества ребер, а V — множества вершин)

Цитата(Kurt @ 19.10.2004, 22:08)

он же всегда вернет 65535... Блин, или вообще ни разу не зайдет в if..

Посмотри, там сразу после цикла инициализации есть строчка

Код

d[s]:=0;

в которой мы показываем, что путь из s в s равен 0.

Далее в этом цикле мы возьмем вершину mI, в которой значение d будет минимальным (на первом шаге это будет именно s). Делаем пометки в массивы про эту вершину типа Q[mI]=0. Потом для каждой вершины, соединенной ребром с mI мы обновим значение d если это будет нужно. Ну и дальше делаем все с начала...
То есть работает по жадному методу (когда выбираем mI).

Массив W вроде действительно не нужен. (Я видимо когда писал этот код записывал в W порядок следования найденых вершин mI - вот что именно отображает этот массив).

Код точно работает правильно - протестировал.

Это сообщение отредактировал(а) Morpheus - 20.10.2004, 16:38

А реальны пересадки с автобуса на автобус?

neutrino В смысле если ехать из Киева в Москву через Чикаго двумя самолетами, то конечно реально... Это и есть метод "релаксации"

Извините, А этот Дийкстра - это разве не кротчайший путь в графе из точки А в точку Б? А как же пересадки?

neutrino Смотри.
Граф задаем так: если есть автобус из A в B, то есть дуга AB, вес которой - стоимость проезда. Тогда Дейкстра как раз и найдет минимальной по стоимости проезда путь. При этом количество пересадок - количество вершин, пройденных по пути.

З.Ы. Важно, что Дейкстра ищет именно минимальный по стоимости цикл а не колличеству пересадок. То есть если будет дешевле выходить на каждой остановке с учетом того, что кондуктор не успеет взять за проезд и стоимость между двумя соседними остановками будет 0, то дейкстра заставит постоянно выходить из автобуса и ждать следующего.

ВОТ Я ДУРАК!!!

Это ведь так просто! А я со своим Г.А. га га га га

Спасибо, Morpheus

Оказалось не все так просто ... Сложность получается O(2^n*n^2). Н в квадрате дает Дейкстра, плюс на каждой из н остановок можно либо выйти либо войти в автобус. И того 2 варианта на н остановок - 2 в степени н. Для ста тысяч остановок комп заглохнет надолго ... Без эвристик не обойтись ...

Цитата

плюс на каждой из н остановок можно либо выйти либо войти в автобус.

Мы друг друга не понимаем

Цитата(Fedor @ 5.1.2005, 23:04)

Мы друг друга не понимаем

Я что-то не понял. А кто из вас Федор и кто Морфеус?

А на счет сложности алгоритма - попробуй анализировать. У меня получилось именно так. Ведь на каждой остановке можно либо выйти либо остаться в автобусе. 2 варианта. А остановок n значит всего вариантов 2^n. Да еще и Дийкстра дает n в квадрате.

Цитата(neutrino @ 4.2.2005, 10:59)

Я что-то не понял. А кто из вас Федор и кто Морфеус?

Ну... Федор==Морфеус.