Что такое минимальный путь в графе?
В теории графов, в чем разница между минимальным расстоянием (которое находит алгоритм Дейкстры) и минимальным путем (я не уверен, что это такое)?
Ответы 6
Я не уверен на 100%, но похоже, что минимальный путь - это список вершин, посещаемых при прохождении пути минимального расстояния от вершины A до вершины B.
Минимальное расстояние такое же, как и минимальный путь.
Минимальное расстояние = наименьшая сумма краевых весов. Минимальный путь = наименьшее количество ребер.
Т.е. // Это более короткий путь из Ванкувера в Торонто, а затем в Винипег, хотя это более короткое расстояние, чтобы лететь из Ванкувера в Калгари в Реджайну, а затем в Винипег.
Обновлено: я думаю, переверните это.
Минимальный путь - это набор ребер, которые при прохождении покрывают наименьшее расстояние между двумя ребрами. Минимальное расстояние - это сумма расстояний между краями минимального пути.
расстояние скалярное; число. path - это список пар вершина / ребро?
Позвольте мне ответить на этот вопрос в рамках сети с источником и приемником. Я хотел бы различать кратчайший путь и минимальный путь, где путь определяется набором ребер.
Кратчайший путь - это путь от источника до приемника, имеющий кратчайшее соответствующее расстояние. Минимальным путем может быть любой путь, который соединяет источник с приемником, пока
и) не содержит циклов; и
ii) удаление любого из ребер с пути означает, что больше нет связи между источником и приемником.