Да, вы правы Алгоритм Прима работает как алгоритм Дейкстры, но в алгоритме Прима он не должен вычислять кратчайший путь из i в j с отрицательными ребрами. Итак, это другой алгоритм, т.е. алгоритм Беллмана-Форда для вычисления кратчайшего пути от i до j с отрицательным краем.
Почему работает алгоритм Прима?
В информатике алгоритм Прима (также известный как алгоритм Ярника) является жадным алгоритмом, который находит минимальное остовное дерево для взвешенного неориентированного графа Это означает, что он находит подмножество ребра, образующие дерево, включающее все вершины, где общий вес всех ребер в дереве минимален.
Правилен ли алгоритм Прима?
Доказательство правильности
Мы доказываем правильность алгоритма Прима индукцией по растущему дереву, построенному алгоритмом. … Мы доказываем сжатием, что Ti является частью минимального остовного дерева. Пусть ei=(v, u) - ребро, найденное алгоритмом Прима, и предположим, что оно не является ребром минимального остовного дерева.
Насколько эффективен алгоритм Прима?
Алгоритм Прима работает эффективно, если мы храним список d[v] самых дешевых весов, которые соединяют вершину v, которой нет в дереве, с любой уже существующей вершиной в дереве. …
Работают ли примитивы с отрицательными весами?
Прим? Решение: Да, оба алгоритма работают с отрицательными весами ребер, потому что свойство cut все еще применяется.
