MATLAB: Find the shortest path

shortest path

i have 2 set of coordinates S1-S25 (set 1) and D1-D10 (set2)

i have connection between coordinates

my start points are from set1 and destination points from set2

if i select start and destination points, and i can go only through the path that has connection

how to reach destination using the given path, also i need to use shortest path

eg: i need to go from S7 to D8, using the specified path

Best Answer

There are a number of implementations of Dijkstra's algorithm on the File Exchange,

https://www.mathworks.com/matlabcentral/fileexchange?q=Dijkstra+shortest+path

Related Solutions

MATLAB: Calculating all paths from a given node in a digraph

I've not tested it thoroughly but I think this should work:

function paths = getpaths(g)
    %return all paths from a DAG.
    %the function will error in toposort if the graph is not a DAG
    paths = {};     %path computed so far
    endnodes = [];  %current end node of each path for easier tracking
   for nid = toposort(g)    %iterate over all nodes
        if indegree(g, nid) == 0    %node is a root, simply add it for now
            paths = [paths; nid]; %#ok<AGROW>

            endnodes = [endnodes; nid]; %#ok<AGROW>
        end
        %find successors of current node and replace all paths that end with the current node with cartesian product of paths and successors
        toreplace = endnodes == nid;    %all paths that need to be edited
        s = successors(g, nid);
        if ~isempty(s)
            [p, tails] = ndgrid(paths(toreplace), s);  %cartesian product
            paths = [cellfun(@(p, t) [p, t], p(:), num2cell(tails(:)), 'UniformOutput', false);  %append paths and successors
                 paths(~toreplace)];
            endnodes = [tails(:); endnodes(~toreplace)];
        end
   end
end

Best Answer

Related Solutions

MATLAB: Calculating all paths from a given node in a digraph

Related Question