2

Не могу понять, откуда берутся значения веса рёбер в примерах алгоритма Дейкстры. Когда из начальной вершины S (кратчайший путь равен нулю,предшествующих вершин нет) до ближайших вершин t и у веса рёбер равны 6 и 4 соответственно... мне непонятно откуда берутся эти значения? Это произвольное расстояние (или время) или они как-то определяются?

2
  • Если у Вас в задаче нет весов (все рёбра равнозначны) - то считайте их веса равными единице. Или любому другому, но положительному и равному для всех рёбер, значению. С другой стороны, если веса рёбер не заданы, то разумнее применять более простой, например, волновой алгоритм.
    – Akina
    22 сен 2017 в 6:29
  • 1
    В реальной жизни за весом будет стоять реальное расстояние по данной дороге или время проезда по ней или какая нибудь другая физическая величина, влияющая на выгодность пути в графе. А если это просто отвлеченная задача на составление алгоритма, то эти числа взяты абсолютно от туда же откуда и в задаче "у Васи было 6 яблок, а у Маши 4 яблока, сколько всего яблок у Васи с Машей", т.е. практически с потолка
    – Mike
    22 сен 2017 в 6:38

2 ответа 2

6

Вообще-то алгоритм Дейкстры работает для взвешенного графа с неотрицательными весами ребер.

Естественно, что во взвешенном графе каждое ребро имеет свой вес. Так что эти значения весов ребер не "берутся откуда-то", а являются неотъемлемыми свойствами графа. В данном случае - графа, использованного (достаточно произвольно) в качестве примера для алгоритма Дейкстры.

Т.е. в определенном смысле они произвольны - но только в том смысле, что в качестве примера мог бы быть использован и другой граф, с другими весами ребер...

Внесу в ответ дополнение из комментария:

Представим, что вам нужно рассказать школьнику об умножении в столбик. Вы рассказываете, как переносятся разряды, как умножаются цифры... Говорите - умножим, например, 123 на 456.
А он вас спрашивает - я не понимаю, откуда при умножении берутся эти 3*6 вначале? Они произвольные или нет?
Как вы ответите? С одной стороны, они вроде бы произвольные, но с другой - они там только потому, что вы уже выбрали в качестве примера 123*456, и поэтому они там просто должны быть - именно 3 и 6. Потому что (произвольно) выбраны 123 и 456.
Вы можете выбрать другие числа, скажем, 327 и 658, и начать с умножения 7 на 8, но вы не можете, выбрав 123 и 456, умножать 7 на 8...
Так понятнее?

4
  • Это я и так знал,я не могу понять пример в котором берутся произвольные значения..А вы пишите вроде бы они произвольные,а вроде бы это свойство алгоритма Дейкстры...мне всё ещё не понятно 22 сен 2017 в 5:54
  • 1
    Представим, что вам нужно рассказать школьнику об умножении в столбик. Вы рассказываете, как переносятся разряды, как умножаются цифры... Говорите - умножим, например, 123 на 456. А он вас спрашивает - я не понимаю, откуда при умножении берутся эти 3*6 вначале? Они произвольные или нет? Как вы ответите? С одной стороны они вроде как и произвольные, но с другой - они там потому, что вы уже выбрали 123*456, и поэтому они там просто должны быть - 3 и 6, Потому что выбраны (произвольно) 123 и 456. Вы можете выбрать 327 на 658, но не можете, выбрав 123 и 456, умножать 7 на 8... Так понятнее?
    – Harry
    22 сен 2017 в 6:20
  • 1
    Возможно понятнее будет так. У Вас есть взвешенный граф (в реальности это могут быть: города с дорогами (км или часы), планеты с а.е., компы и время доступа/передачи данных) и т.д.). И вот к этому графу применяется алгоритм. Веса уже должны быть, это входной параметр. Алгоритм их лишь использует. Как Вам привели пример выше: f(x,y)=(чему-то), x,y это входные параметры, как в умножении, сложении и т.д.
    – Dejsving
    22 сен 2017 в 6:25
  • Да,спасибо всем.. теперь более менее проясняется) 22 сен 2017 в 11:24
1

Полагаю, вы имеете в виду, какая структура отвечает за задание длины рёбрам. Если это так, то вес рёбер задаётся в таблице смежностей.

В ней количество столбцов и рядков равно количеству вершин. В ячейке (a, b) содержится путь (Его длина или стоимость) от a до b. Если пройти невозможно, обычно ставят какое-нибудь высокое константное значение, которое условно принимают за бесконечность (Бесконечный путь -> пройти нельзя).

Обычно это максимальное число типа делённое на два, чтобы при сложении вы не выпали в отрицательный диапазон и не нашли ошибочный путь.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.