Algorithm: All Pairs- / Single Source Shortest Path

[mknblch]

A Single Source Shortest Path algorithms calculates a path between a pair of nodes whose summed weights are minimal. A common algorithm used is Dijkstra. All Pairs Shortest Path on the other hand calculates a shortest path forest containing all paths between the nodes in the graph. An algorithm to solve this is Floyd Warshall or Parallel Johnson's algorithm.

Progress

• [x] single threaded implementation
• [x] tests
• [x] simple benchmark
• [x] implement procedure
• [x] benchmark on bigger graphs
• [x] parallelization

Requirements

(Outgoing)RelationshipIterator & Weights

Data structured involved

• An int-based Fibonacci Heap which implements an efficient priority queue.
• Different Container for Costs / visited state / paths

ToDo

benchmark

Implement benchmark on big graph

parallelization

Parallizing All Pairs Shortest Path might be easy using Dijkstra on each thread for a different node. An easy approach for Single Source SP may use two threads. One starting at the start-node, one at the end-node. The first wins. More

evaluation

• Performance tests on different dataset sizes / level of concurrency

[mknblch]

Another paper with an alternative approach to parallel SSSP: http://www.cc.gatech.edu/~bader/papers/ShortestPaths-ALENEX2007.pdf

[mknblch]

Also https://arxiv.org/pdf/1604.02113v1.pdf