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

Question

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

Пример:

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

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

Answer 1

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

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

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

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