ФорумПрограммированиеPHP для идиотов → Задача нахождения кратчайчего пути в графе

Задача нахождения кратчайчего пути в графе

  • chuche

    Сообщения: 7 Репутация: N Группа: Кто попало

    Spritz 3 февраля 2011 г. 17:53

    Алгори́тм Де́йкстры (Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов.
    Примеры

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

    Вариант 2. Имеется некоторое количество авиарейсов между городами мира, для каждого известна стоимость. Стоимость перелёта из A в B может быть не равна стоимости перелёта из B в A. Найти маршрут минимальной стоимости (возможно, с пересадками) от Копенгагена до Барнаула.


    class dilizhans {
    public $arrput;
    public $cena;
    }

    class rebro {
    public $nach_tochka;
    public $kon_tochka;
    public $cena_rebra;
    }

    $mas = file_get_contents ('C:\Users\Антон\Desktop\rebra.txt');
    $arr_rebra = explode("\n",$mas);

    for($i=0;$i<count($arr_rebra);$i=$i+4)
    {
    $graf[] = new rebro();
    $graf[count($graf)-1]->nach_tochka=$arr_rebra[$i];
    $graf[count($graf)-1]->kon_tochka=$arr_rebra[$i+1];
    $graf[count($graf)-1]->cena_rebra=$arr_rebra[$i+2];
    }

    //echo "<pre>";
    //print_r($graf);
    //echo "</pre>";

    $work[] = new dilizhans();
    $work[count($work)-1]->arrput[]=1;
    $work[count($work)-1]->cena=0;

    //echo "<pre>";
    //print_r($work);
    //echo "</pre>";

    $i=0;
    while ($i<20) {

    $n=$work[$i]->arrput[count($work[$i]->arrput)-1];

    if ($work[$i]->arrput[count($work[$i]->arrput)-1]<10)
    { for($j=0;$j<count($graf);$j++)
    {
    if($graf[$j]->nach_tochka==$n)
    {
    $work[] = new dilizhans();
    $work[count($work)-1]->arrput=$work[$i]->arrput;
    $work[count($work)-1]->arrput[]=$graf[$j]->kon_tochka;
    $work[count($work)-1]->cena=$work[$i]->cena+$graf[$j]->cena_rebra;
    }
    }

    $work[$i]->cena=0;

    }
    $i++;
    }

    for ($i=0;$i<count($work);$i++)
    {
    if ($work[$i]->arrput[count($work[$i]->arrput)-1]==10&&$work[$i]->cena!=0)
    {var_dump($work[$i]);echo "<br>";}
    }
    Спустя 139 сек.
    Информация в txt файле хранится в таком формате:
    1 - номер начальной точки
    2 - номер конечной точки
    1 - длинна ребра

    1
    3
    2

    1
    4
    3

    2
    5
    3

    2
    3
    3

    3
    6
    6

    3
    7
    4

    4
    7
    9

    5
    8
    5

    5
    6
    2

    6
    8
    7

    6
    9
    1

    7
    9
    1

    8
    10
    9

    9
    10
    3
  • phpdude

    Сообщения: 26624 Репутация: N Группа: в ухо

    Spritz 3 февраля 2011 г. 18:16, спустя 23 минуты 16 секунд

    \��нтон

    ребус? Гантон? я угадал?
    Сапожник без сапог
  • master

    Сообщения: 3236 Репутация: N Группа: Джедаи

    Spritz 3 февраля 2011 г. 18:45, спустя 29 минут 15 секунд

    Гантон?

    Ну почему же, может юзера так и зовут ��нтон
    не всё полезно, что в swap полезло
  • Timur

    Сообщения: 1068 Репутация: N Группа: Джедаи

    Spritz 4 февраля 2011 г. 7:05, спустя 12 часов 20 минут 2 секунды

    1) chuche, у тебя какие-то вопросы по алгоритму или ты хочешь его обсудить или просто решил поделится реализацией или что?
    2) Открой для себя Google Translate. kon_tochka и arr_rebra ― это пиздец.
  • Sinkler

    Сообщения: 7931 Репутация: N Группа: в ухо

    Spritz 4 февраля 2011 г. 7:08, спустя 2 минуты 27 секунд

    chuche, у тебя какие-то вопросы по алгоритму или ты хочешь его обсудить или просто решил поделится реализацией или что?

    по ходу люди думают, что тут, как на хабре)))
  • Абырвалг

    Сообщения: 6476 Репутация: N Группа: Джедаи

    Spritz 4 февраля 2011 г. 7:40, спустя 32 минуты 21 секунду

    Timur, лучше лингво
  • technobulka

    Сообщения: 4540 Репутация: N Группа: Джедаи

    Spritz 4 февраля 2011 г. 9:35, спустя 1 час 54 минуты 59 секунд

    Абырвалг, лучше дуд-транслейт))
    Высокоуровневое абстрактное говно
  • Rotten

    Сообщения: 2243 Репутация: N Группа: Адекваты

    Spritz 4 февраля 2011 г. 10:19, спустя 44 минуты 23 секунды

    Я ненавижу… очень ненавижу кодеров которые обзывают переменные транслитом.
    Хуево знаешь английский? Переведи слово в гугле и заюзай нормальный вариант, только ради всего святого - не уродуй код… не нужно вешать на него рагульский ярлык…
    Мне каждый раз грустно стает когда представляю что подумает забугорный кодер если бы поглядел на этот код…
    Будьте культурными.
  • Frozzeg

    Сообщения: 5641 Репутация: N Группа: Джедаи

    Spritz 4 февраля 2011 г. 10:52, спустя 32 минуты 43 секунды

    че их ненавидеть? видишь транслит - шли нахуй, делов-то
    You can be anything you want to be. Just turn yourself into anything you think that you could ever be.
  • kostyl

    Сообщения: 5203 Репутация: N Группа: Джедаи

    Spritz 4 февраля 2011 г. 11:08, спустя 15 минут 48 секунд

    гугл транслейт использует лингву
  • Rotten

    Сообщения: 2243 Репутация: N Группа: Адекваты

    Spritz 4 февраля 2011 г. 11:47, спустя 38 минут 51 секунду

    kostyl,
    гугл транслейт использует лингву

    Ой очень сомневаюсь: у них программистов невьебенное море. Зачем тогда тырить(читай - покупать) чтото готовое в 3rd party company?
    Я не верю в то чтобы они разрабатывали на основе чегото свои вещи… Чем тогда будет заниматся та бесконечная толпа кодеров?


    Это как в майкрософте - им делать нехер вотт потому и страдают показухой как они "хоронят айпад"… Понанимали народу для претижа, а толку?
  • Frozzeg

    Сообщения: 5641 Репутация: N Группа: Джедаи

    Spritz 4 февраля 2011 г. 11:50, спустя 2 минуты 55 секунд

    Я не верю в то чтобы они разрабатывали на основе чегото свои вещи…

    :D о гугл хром слышал?
    Спустя 94 сек.
    в то что компании юзают готовые игровые движки, вместо того чтобы все написать с нуля, тоже не веришь? ведь у них так много людей..
    You can be anything you want to be. Just turn yourself into anything you think that you could ever be.
  • Rotten

    Сообщения: 2243 Репутация: N Группа: Адекваты

    Spritz 4 февраля 2011 г. 12:32, спустя 42 минуты 45 секунд

    Frozzeg, да не.. я не говорю о своих наработках…
    Просто покупать какойто двиг Лингво и на нем строить словарь… я не знаю.. Да, с 1й стороны эти мильярдеры могуть се позволить не только это а вообще купить этот весь ABBYY…
    С другой стороны - Гугл это "свой фирменный рецепт"… Их приложения действительно довольно уникальны в том смысле что хоршенко отличаются от остальной массы..

    Они - отвечают за то что пишут прежде всего качеством и надежностю. Ихними продуктами пользуются чаще других (да, в том числе и майкрософты и прочее)…
    Взять чужой двиг и тупо "сменить на нем одежду" - не всегда значит сэкономить время и не изобретать велик. Напротив - это значит что придется весь этот код перерывать на наличие ошибок и прочих тонкостей архитекуры которые могут оказатся несовместимыми с ожидаемыми изминениями…

    Короче говоря - ответственность за работоспособность этого ПО - не полная, ибо остальная сать висит какраз на этом чужом двиге, котоым занимались левые разрабы…
    Выпускать такой продукт - страшновато, мягко говоря…
    Спустя 147 сек.
    Исключение может составить разве база данных слов для перевода: вот ее то составлять какраз действительно очень муторно и долго…
    Потому заплатить за нее нехилие денежки - отнюдь не жалко…
  • master

    Сообщения: 3236 Репутация: N Группа: Джедаи

    Spritz 16 февраля 2011 г. 15:11, спустя 12 дней 2 часа 38 минут

    На сегодняшний день важна скорость разработки. Купить готовый продукт - быстрее чем разрабатывать самому, даже если разработка будет чуть дешевле в деньгах. Купить - дешевле чем делать самим, а спиздить - дешевле чем купить. Все это прекрасно понимают.
    не всё полезно, что в swap полезло
  • MoonEvil

    Сообщения: 21 Репутация: N Группа: Кто попало

    Spritz 17 февраля 2011 г. 4:54, спустя 13 часов 43 минуты 10 секунд

    $_SERVER['DOCUMENT_ROOT']

Пожалуйста, авторизуйтесь, чтобы написать комментарий!