Что такое минимальный путь в графе?

Question

В теории графов, каково различие между минимальным расстоянием (которое находит алгоритм Дейкстры) и минимальным путем (который я не уверен, что это)?

Answer 1

Минимальный путь - это набор ребер, которые при прохождении охватывают наименьшее расстояние между двумя ребрами. Минимальное расстояние - это сумма расстояния между краями минимального пути.

Answer 2

расстояние скалярно; число. путь - это список пар вершин / ребер?

Answer 3

Минимальное расстояние = наименьшая сумма весов ребер. Минимальный путь = наименьшие ребра.

Т.е. // Это более короткий путь, чтобы лететь из Ванкувера в Торонто, а затем в Винипег, хотя это более короткое расстояние, чтобы лететь из Ванкувера в Калгари и Реджайну, а затем в Винипег.

Редактировать: Думаю, переверни это.

Answer 4

Позвольте мне ответить на этот вопрос в рамках сети с источником и приемником. Я хотел бы различать кратчайший путь и минимальный путь, где путь определяется набором ребер.

Кратчайший путь - это путь от источника к стоку, который имеет самое короткое соответствующее расстояние. Минимальным путем может быть любой путь, соединяющий источник с приемником, если

i) не содержит циклов; и

ii) удаление любого ребра с пути означает, что больше нет связи между источником и приемником.

Answer 5

Минимальное расстояние соответствует минимальному пути.

Answer 6

Я не уверен на 100%, но звучит так, будто минимальный путь будет списком посещенных вершин при прохождении пути минимального расстояния от вершины A до вершины B.