implementation of djikstras, need to find the logic to print the path and its implementation

1 次查看（过去 30 天）

Alan Antony 2019-9-23

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/481673-implementation-of-djikstras-need-to-find-the-logic-to-print-the-path-and-its-implementation

关闭： MATLAB Answer Bot 2021-8-20

I have here implemented the dijkstras on a sample graph ..... but im not getting the logic how to store the path and print the shortest path through the nodes.. need help

i will share the codes here.

function [path] = myShortestpath(G, s, t)
    nodes = [3, -2; ...
             3, -1; ...
             3, 1; ...
             13, -1; ...
             12, -1; ...
             1,-1; ...
             1, 1; ...
             14,-1; ...
             11,-1; ...
             2, -1; ...
             2, 1; ...
             ];
    G =     [1, 2, 1.0; ...
             2, 1, 1.0; ...
             3, 4, 4.0; ...
             4, 6, 4.5; ...
             6, 5, 3.0; ...
             5, 3, 3.5; ...
             6, 9, 5.0; ...
             9, 10, 4.0; ...
             10, 8, 5.0; ...
             8, 6, 4.0; ...
             ];
    s=3;
    t=8;
    nodeNames = cell.empty;
    num_nodes = size(nodes, 1);
    for iN = 1:num_nodes
       curName = sprintf('(%i|%i)', nodes(iN, 1), nodes(iN, 2));
       nodeNames = [nodeNames, curName]; %#ok<AGROW>
    end
  % Convert graph to digraph object
  dg = digraph(G(:, 1), G(:,2), G(:,3), nodeNames);    
  plot (dg);
   
  %num_vertices= size(G,1);
  visited_vertices(1:num_nodes) = false;
  distance(1:num_nodes) = inf;
  distance(s)=0;
  %weights= G(:,3);
  weightMatrix = zeros(num_nodes, num_nodes);
  weightMatrix(sub2ind(size(weightMatrix), G(:,1), G(:,2))) = G(:,3);
  %exch_init_distance = 1;
  previous=[];
for v = 1:num_nodes-1
    vertex_minimum = minimum_vertex(distance, visited_vertices, num_nodes);
    visited_vertices(vertex_minimum) = true;
    
    for toNode = 1: num_nodes
         if (weightMatrix(vertex_minimum,toNode)~= 0 && ~(visited_vertices(toNode)))
            temp_distance = distance(vertex_minimum) + weightMatrix(vertex_minimum,toNode);
             if (temp_distance < distance(toNode))
               distance(toNode) = temp_distance;
               previous(toNode) = vertex_minimum;
               %exch_init_distance = distance(toNode);
               
            end
        end
    end
end
end