Разница между основным алгоритмом кратчайшего пути и MST-графиком

Question

Не удалось найти сводный ответ на этот вопрос. Так что поставь это здесь и отвечай сам.

Answer 1

Кратчайший путь

1. Алгоритм Дейкстры

Single Source Shortest Path
Greedy Algorithm
Works for directed and undirected graphs
Does not work for negative edges and cannot detect negative cycles
Time Complexity O(E*log(V))

2. Алгоритм Беллмана-Форда

Single Source Shortest Path
Dynamic Programming
Works for directed and undirected graphs
Works on negative edges and detects negative edge cycles
Time Complexity O(V*E)

3. Алгоритм Флойда-Варшалла

All Source Shortest Path
Dynamic Programming
Works for directed and undirected graphs
Works on negative edges but cannot detect negative cycles
Time Complexity O(V3)

Минимальное остовное дерево

1. Алгоритм Прима

Greedy Algorithm
Starts from any vertex
Does not work for directed graphs
Does not work on disconnected graphs
An edge may be considered multiple times
Better for dense graphs
Time Complexity O(E*log(V)) with Binary heap and O(E + V*log(V)) with Fibonacci heap

2. Алгоритм Крускала

Greedy Algorithm
Starts from smallest edge
Does not work for directed graphs
Works on disconnected graphs
An edge is considered only once
Better for sparse graphs
Time Complexity O (E*log(v))