Могу ли я использовать алгоритм Прима вместо алгоритма Дейкстры для поиска кратчайшего пути?

Я весь день боролся за понимание алгоритма Дейкстры и его реализацию без каких-либо значительных результатов. У меня есть матрица городов и их расстояний. Что я хочу сделать, так это указать точку отправления и точку назначения, чтобы найти кратчайший путь между городами.

Пример:

     __0__ __1__ __2__ 
 0  |  0  | 34  |  0  |
    |-----|-----|-----|
 1  | 34  |  0  | 23  |
    |-----|-----|-----|
 2  |  0  | 23  |  0  |
     ----- ----- -----

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


shortest-path dijkstra prims-algorithm minimum-spanning-tree
person Pithikos    schedule 20.03.2011    source источник

Ответы (1)


arrow_upward
5
arrow_downward

Вы можете применить алгоритм Прима, а затем пройтись по полученному дереву, но ваш ответ может быть неправильным. Предположим, что у вас есть граф, в котором каждое ребро имеет одинаковый вес. Алгоритм Прима просто выбирает ребро минимального веса в наборе ребер, которые можно добавить к дереву. Возможно, вы не выберете ребро, которое приведет к кратчайшему пути между двумя узлами. Предполагать:

     __0__ __1__ __2__ 
 0  |  0  |  1  |  1  |
    |-----|-----|-----|
 1  |  1  |  0  |  1  |
    |-----|-----|-----|
 2  |  1  |  1  |  0  |
     ----- ----- -----

Начиная с узла 0, вы можете с помощью Прима выбрать ребра 0-1 и 0-2, чтобы сделать свое дерево. В качестве альтернативы вы можете выбрать ребра 0-1 и 1-2, чтобы сделать свое дерево. Под первым набором ребер можно найти путь минимальной длины от 0 до 2, но под вторым набором ребер вы не найдете минимальный путь. Поскольку вы не можете априори определить, какие ребра добавляются в алгоритм Prim, вы не можете использовать его для поиска кратчайшего пути.

Вы можете рассмотреть алгоритм Bellman-Ford, но если вы не имеете дело с отрицательными весами ребер я считаю предпочтительным алгоритм Дейкстры.

person John Percival Hackworth    schedule 20.03.2011
comment
Спасибо! Это рассортировало много вещей в моей голове. Я думаю, что на вашем примере я также лучше понял алгоритм Дейкстры, а именно важность переменной стоимости. - person Pithikos; 20.03.2011