Tag: MIT

All-Pairs Shortest Paths – Floyd Warshall Algorithm

Given a set of vertices V in a weighted graph where its edge weights w(u, v) can be negative, find the shortest-path weights d(s, v) from every source s for all vertices v present in the graph. If the graph contains negative-weight cycle, report it.

Single-Source Shortest Paths – Bellman Ford Algorithm

Given a source vertex s from set of vertices V in a weighted graph where its edge weights w(u, v) can be negative, find the shortest-path weights d(s, v) from given source s for all vertices v present in the graph. If the graph contains negative-weight cycle, report it.