implementation of djikstras, need to find the logic to print the path and its implementation
Info
This question is closed. Reopen it to edit or answer.
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?
Alan Antony
on 24 Sep 2019
Answers (0)
This question is closed.
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!