Info

この質問は閉じられています。 編集または回答するには再度開いてください。

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

2 ビュー (過去 30 日間)
Alan Antony
Alan Antony 2019 年 9 月 23 日
閉鎖済み: 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
  2 件のコメント
Akira Agata
Akira Agata 2019 年 9 月 23 日
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 2019 年 9 月 24 日
i had got it implemented , but thanks for the reply..... will post more if i have more doubts

回答 (0 件)

この質問は閉じられています。

Community Treasure Hunt

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

Start Hunting!

Translated by