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

Question

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

Answer 1

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

Answer 2

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

Answer 3

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

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

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

Answer 4

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

Answer 5

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

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

<р> я) он не содержит циклов; и

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

Answer 6

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