Effacer les filtres
Effacer les filtres

Info

Cette question est clôturée. Rouvrir pour modifier ou répondre.

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

1 vue (au cours des 30 derniers jours)
Alan Antony
Alan Antony le 23 Sep 2019
Clôturé : MATLAB Answer Bot le 20 Août 2021
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 commentaires
Akira Agata
Akira Agata le 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
Alan Antony le 24 Sep 2019
i had got it implemented , but thanks for the reply..... will post more if i have more doubts

Réponses (0)

Cette question est clôturée.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by