Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Консультации по дискретной математике

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 106 RSS
←   Май 2011   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Сайт рассылки: http://rusfaq.ru/issues/8/19/525
Открыта: 17-04-2009

Автор
Калашников О.А.

Статистика

106 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Консультации по дискретной математике


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный ХОСТИНГ на базе Linux x64 и Windows x64

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты данной рассылки

Асмик Александровна
Статус: Академик
Рейтинг: 8086
∙ повысить рейтинг » 		Абаянцев Юрий Леонидович aka Ayl
Статус: Профессионал
Рейтинг: 2270
∙ повысить рейтинг » 		Жерар
Статус: Профессор
Рейтинг: 2151
∙ повысить рейтинг »

/ НАУКА И ОБРАЗОВАНИЕ / Точные и естественные науки / Математика дискретная

Номер выпуска:243
Дата выхода:22.05.2011, 15:30
Администратор рассылки:Асмик Александровна (Академик)
Подписчиков / экспертов:57 / 65
Вопросов / ответов:1 / 1

Вопрос № 183210: Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос: В заданном графе алгоритмом Дейкстры найти кратчайший путь от начальной вершины до конечной

Вопрос № 183210:

Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос:
В заданном графе алгоритмом Дейкстры найти кратчайший путь от начальной вершины до конечной

Номер начальной вершины 2, номер конечной вершины 10.
Заранее спасибо.

Отправлен: 17.05.2011, 14:56
Вопрос задал: Егерев Юрий (Посетитель)
Всего ответов: 1
Страница вопроса »

Отвечает Асмик Александровна (Академик) :
Здравствуйте, Егерев Юрий!

В алгоритме Дейкстры вводятся вспомогательные массивы T[1..p] - массив длин кратчайшего пути от s данной вершины.
X[1..p] - булевское значение, показывающее, что путь найден.
H[1..p] - массив вершин, предшействующих в кратчайшем пути данной.
Вначале массив T инициализируется ∞, все X[v]=0
Отмечаем вершину 2.
T[2]=0
X[2]=1
H[2]=0

T={∞,0,∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞}
X={0, 1, 0, 0, 0, 0, 0, 0, 0, 0 }
Обходим все непомеченные вершины, смежные с 2.
Если для вершины u T[u]>T[v]+C[v,u], найден более короткий путь из s в u через м. Запоминаем его.
T[1]=1 H[1]=2
T[4]=6 H[4]=2
T[5]=7 H[5]=2
Кратчайший путь из всех полученных - путь к вершине 1. Помечаем ее.
X[1]=1
T={1, 0, ∞, 6, 7, ∞, ∞, ∞, ∞, ∞}
X={1, 1, 0, 0, 0, 0, 0, 0, 0, 0 }
Назначаем 1 текущей.

Обходим все непомеченные в ершины, смежные с 1.
T[3]=4 H[1]=1
Кратчайший путь из всех полученных - путь к вершине 3. Помечаем ее.
X[3]=1
Назначаем его текущим.
T={1, 0, 4, 6, 7, ∞, ∞, ∞, ∞, ∞}
X={1, 1, 1, 0, 0, 0, 0, 0, 0, 0 }

Обходим все непомеченные вершины, смежные с 3.
T[6]=8 H[6]=3
Кратчайший путь из всех полученных - путь к вершине 4(полученный на первом шаге). Помечаем ее.
X[4]=1
Назначаем его текущим.
T={1, 0, 4, 6, 7, 8, ∞, ∞, ∞, ∞}
X={1, 1, 1, 1, 0, 0, 0, 0, 0, 0 }

Обходим все непомеченные вершины, смежные с 4.
T[7]=15 H[7]=4
Кратчайший путь из всех полученных - путь к вершине 5. Помечаем ее.
X[5]=1
Назначаем его текущим.
T={1, 0, 4, 6, 7, 8, 15, ∞, ∞, ∞}
X={1, 1, 1, 1, 1, 0, 0, 0, 0, 0}

Обходим все непомеченные вершины, смежные с 5.
Путь к вершине 7 через 5 оказывается более коротким, чем через 4.
T[7]=9 H[7]=5
Кратчайший пу ть из всех полученных - путь к вершине 6. Помечаем ее.
X[6]=1
Назначаем его текущим.
T={1, 0, 4, 6, 7, 8, 9, ∞, ∞, ∞}
X={1, 1, 1, 1, 1, 1, 0, 0, 0, 0}

Обходим все непомеченные вершины, смежные с 6.
T[9]=14 H[9]=6
Кратчайший путь из всех полученных - путь к вершине 7. Помечаем ее.
X[7]=1
Назначаем его текущим.
T={1, 0, 4, 6, 7, 8, 9, ∞, 14, ∞}
X={1, 1, 1, 1, 1, 1, 1, 0, 0, 0}

Обходим все непомеченные вершины, смежные с 7.
T[10]=13 H[10]=7
T[8]=16 H[8]=7
Кратчайший путь из всех полученных - путь к вершине 10. Помечаем ее.
Так как 10 - это конечная вершина, алгоритм закончен.
T={1, 0, 4, 6, 7, 8, 9, ∞, 14, 13}
X={1, 1, 1, 1, 1, 1, 1, 0, 0, 1}
Кратчайший путь к из 2 к 10 проходит через 5 и 7 и равен 13.

Ответ отправил: Асмик Александровна (Академик)
Ответ отправлен: 17.05.2011, 15:57
Номер ответа: 267208
Армения, Ереван
Адрес сайта: http://hasmikg.narod.ru

Оценка ответа: 5

Вам помог ответ? Пожалуйста, поблагодарите эксперта за это!
Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 267208 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:

    • Оценить выпуск »
    Нам очень важно Ваше мнение об этом выпуске рассылки!

    Задать вопрос экспертам этой рассылки »

    Скажите "спасибо" эксперту, который помог Вам!

    Отправьте СМС-сообщение с тестом #thank НОМЕР_ОТВЕТА
    на короткий номер 1151 (Россия)
    Номер ответа и конкретный текст СМС указан внизу каждого ответа.

    Полный список номеров »

    * Стоимость одного СМС-сообщения от 7.15 руб. и зависит от оператора сотовой связи. (полный список тарифов)
    ** При ошибочном вводе номера ответа или текста #thank услуга считается оказанной, денежные средства не возвращаются.
    *** Сумма выплаты эксперту-автору ответа расчитывается из суммы перечислений на портал от биллинговой компании.

    © 2001-2011, Портал RFPRO.RU, Россия
    Авторское право: ООО "Мастер-Эксперт Про"
    Калашников О.А. | Гладенюк А.Г.
    Хостинг: Компания "Московский хостер"
    Версия системы: 2011.6.31 от 07.05.2011
    В избранное