[Lecture Summary] 13 Algorithm and Data Structure : All Pairs Shortest Path

This contents is based on Lecture of link

Overview

All-pairs Shortest Path(APSP) is a different problem, which gets directed graph as an input and returns all the distance values or abort it if the input graphs contains negative weight cycle.

To solve this problem, simply running $V$ times of complexity of SSSP Algorithms. To solve this problem, we’d like to use Dijkstra’s Algorithm which approxiamtely linear to $\mid V\mid^2$.

To do so, all we need to do is manipulating non-negative weighted graphs being preserving shortest path!

However, if there exists negative weight cycles, then shortest path is not simple!

Input: Non-negative weighted graphs

Naively adding positive value to every edge makes bias toward path traversing fewer edges. So we can add $h$ for outgoing edges and subtract $h$ from incoming edges! As a results, weight of path does not changes(it is preserved locally).

$w(\pi) = \sum w(v_{i-1}, v_i) = \sum w(v_{i-1}, v_i) + h(v_{i-1}) - h(v_{i}) = w(\pi) + h(v_0) - h(v_k)$

Now then, all we need to do is determining potential function $h(\cdot)$ so that all the weight of path is positive.

Idea is that we can define potential as distance estimates with virtually added vertices then prove it via triangle inequality. For the distance between virtually added vertices, we set zero weighted edges initially and update them.

Algorithm

• Construct new graph with virtual nodes : $O(\mid V \mid + \mid E \mid)$
• Run Bellman Ford for all the real vertices : $O(\mid V \mid + \mid E \mid)$
• Reweight the new graph : $O(\mid E\mid)$
• For all the real verices, run Dijkstra : $O(\mid V\mid \cdot (\mid V \mid \log \mid V \mid + \mid E \mid))$