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

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, но во втором наборе ребер вы не найдете минимальный путь. Поскольку вы не можете априори определить, какие ребра добавляются в алгоритм Прима, вы не можете использовать его, чтобы найти кратчайший путь.

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