Info
This question is closed. Reopen it to edit or answer.
implementation of djikstras, need to find the logic to print the path and its implementation
1 view (last 30 days)
Show older comments
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
2 Comments
Akira Agata
on 23 Sep 2019
To store the shortest path and print it, MATLAB function shortestpath and its help page will be help.
Or, would you like to implement Dijkstra algorithm by yourself?
Answers (0)
This question is closed.
See Also
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!