／var／logmarcus chiu

Single-Source Shortest Paths Problem

Created on · Last Modified on

Single-Source Shortest Paths Problem
  • is a type of shortest-path problem where given a vertex v we need to find the shortest path TO every other node

Algorithms

Algorithm

Description

Time Complexities

Dijkstra’s Algorithm

O(V2)

Bellman-Ford Algorithm
  • not greedy
  • fails on negative weight cycles because there is no shortest path on graphs with negative weight cycles

O(VE)