Info
Questa domanda è chiusa. Riaprila per modificarla o per rispondere.
implementation of djikstras, need to find the logic to print the path and its implementation
1 visualizzazione (ultimi 30 giorni)
Mostra commenti meno recenti
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 Commenti
Akira Agata
il 23 Set 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?
Risposte (0)
Vedere anche
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!