function [dist,path,pred] = graphshortestpath(G, S, D, NVPArgs)
%GRAPHSHORTESTPATH solves the shortest path problem in graph.
%
% [DIST,PATH,PRED] = GRAPHSHORTESTPATH(G,S) determines the single source
% shortest paths from node S to all other nodes in the graph G. Weights of
% the edges are all nonzero entries in the square adjacency matrix G. DIST
% are the n distances from source to every node (using Inf for
% non-reachable nodes and zero for the source node). The PATH contains the
% winning paths to every node, and PRED contains the predecessor nodes of
% the winning paths.
%
% [DIST,PATH,PRED] = GRAPHSHORTESTPATH(G,S,D) determines the single
% source-single destination shortest path from node S to node D.
%
% GRAPHSHORTESTPATH(...,'METHOD',METHOD) selects the algorithm to use,
% options are:
%    'BFS'          - Breadth First Search, assumes all the weights are
%                     equal, edges are nonzero entries in the sparse matrix
%                     G. Time complexity is O(n+e).
%   ['Dijkstra']    - Assumes that weights of the edges are all positive
%                     values in the sparse matrix G. Time complexity is
%                     O(log(n)*e).
%    'Bellman-Ford' - Assumes that weights of the edges are all nonzero
%                     entries in the sparse matrix G. Time complexity is
%                     O(n*e).
%    'Acyclic'      - The input graph must be acyclic. Assumes that weights
%                     of the edges are all nonzero entries in the sparse
%                     matrix G. Time complexity is O(n+e).
%
% Note: n and e are number of nodes and edges respectively.
%
% GRAPHSHORTESTPATH(...,'DIRECTED',false) indicates that the graph G is
% undirected, upper triangle of the sparse matrix is ignored. Default is
% true.
%
% GRAPHSHORTESTPATH(...,'WEIGHTS',W) provides custom weights for the edges,
% useful to indicate zero valued weights. W is a column vector with one
% entry for every edge in G, traversed column-wise.
%
% Examples:
%   % Create a directed graph with 6 nodes and 11 edges
%   W = [.41 .99 .51 .32 .15 .45 .38 .32 .36 .29 .21];
%   DG = sparse([6 1 2 2 3 4 4 5 5 6 1],[2 6 3 5 4 1 6 3 4 3 5],W)
%   h = view(biograph(DG,[],'ShowWeights','on'))
%   % Find shortest path from 1 to 6
%   [dist,path,pred] = graphshortestpath(DG,1,6)
%   % Mark the nodes and edges of the shortest path
%   set(h.Nodes(path),'Color',[1 0.4 0.4])
%   edges = getedgesbynodeid(h,get(h.Nodes(path),'ID'));
%   set(edges,'LineColor',[1 0 0])
%   set(edges,'LineWidth',1.5)
%
%   % Solving the previous problem for an undirected graph
%   UG = tril(DG + DG')
%   h = view(biograph(UG,[],'ShowArrows','off','ShowWeights','on'))
%   % Find the shortest path between node 1 and 6
%   [dist,path,pred] = graphshortestpath(UG,1,6,'directed',false)
%   % Mark the nodes and edges of the shortest path
%   set(h.Nodes(path),'Color',[1 0.4 0.4])
%   fowEdges = getedgesbynodeid(h,get(h.Nodes(path),'ID'));
%   revEdges = getedgesbynodeid(h,get(h.Nodes(fliplr(path)),'ID'));
%   edges = [fowEdges;revEdges];
%   set(edges,'LineColor',[1 0 0])
%   set(edges,'LineWidth',1.5)
%
% See also: GRAPHALLSHORTESTPATHS, GRAPHCONNCOMP, GRAPHISDAG,
% GRAPHISOMORPHISM, GRAPHISSPANTREE, GRAPHMAXFLOW, GRAPHMINSPANTREE,
% GRAPHPRED2PATH, GRAPHTOPOORDER, GRAPHTRAVERSE.
%
% References:
%  [1]	E.W. Dijkstra "A note on two problems in connexion with graphs"
%       Numerische Mathematik, 1:269-271, 1959.
%  [2]	R. Bellman "On a Routing Problem" Quarterly of Applied Mathematics,
%       16(1):87-90, 1958.

%   Copyright 2006-2021 The MathWorks, Inc.
arguments
    G {bioinfo.internal.ValidationHelper.mustBeAdjacencyGraph}
    S(1,1) double {mustBePositive, mustBeInteger}
    D double = []
    NVPArgs.Directed(1,1) logical = true;
    NVPArgs.Method(1,1) string {bioinfo.internal.ValidationHelper.mustBeMemberCaseInsensitive(NVPArgs.Method, ["BFS", "Dijkstra", "Bellman-Ford", "Acyclic"])} = "Dijkstra"
    NVPArgs.Weights(:,1) {mustBeNumeric, mustBeReal}
end

if nargin > 2
    validateattributes(D, {'double'}, {'scalar', 'positive', 'integer'});
end

conversionArgs = namedargs2cell(rmfield(NVPArgs, 'Method'));
G_graph = bioinfo.internal.biograph2matlab(G, conversionArgs{:});

%Map algorithm to graph implementation
graphAlgorithms =                      {'unweighted', 'positive', 'mixed',        'acyclic'};
algorithmIdx = strcmpi(NVPArgs.Method, ["BFS",        "Dijkstra", "Bellman-Ford", "Acyclic"]);

algorithm = graphAlgorithms{algorithmIdx};

if strcmp(algorithm, 'mixed') && ~NVPArgs.Directed
    algorithm = 'auto'; % Bellman-Ford not compatible with undirected MATLAB graphs, use auto for backwards compatibility
end

if isempty(D)
    % Find all shortest paths
    [path, dist] = shortestpathtree(G_graph, S, 'OutputForm', 'cell', 'Method', algorithm);
    path = path'; % For compatibility, convert to row vector
else
    [path, dist] = shortestpath(G_graph, S, D, 'Method', algorithm);
end

% For compatibility, need to use shortestpathtree to figure out all pred
% nodes, even if we don't need the path to all
if nargout > 2
    pred = shortestpathtree(G_graph, S, 'OutputForm', 'vector', 'Method', algorithm);
end