Compute shortest paths for multiple sources using MATLAB's `graphshortestpath`

Alec Jacobson

March 10, 2014

weblog/

Annoyingly MATLAB's graphshortestpath function implementing Dijkstra's algorithm only computes shortest path to a single source. Given an n-by-n adjacency weight matrix G and a list of m sources S you can compute the shortest path distances in a n-by-m matrix D with:

D = cell2mat(arrayfun(@(s) graphshortestpath(G,s)',S,'UniformOutput',false));