Please finish the coding at the end - There should be only 8 - 10 lines of codin
ID: 3620397 • Letter: P
Question
Please finish the coding at the end - There should be only 8 - 10 lines of coding left.function [d, iN] = dijkstra(n,A,C)
% [d, iN] = dijkstra(n, A, C)
%
% dijkstra.m is a MATLAB function that returns the vector of shortest path
% lengths from node 1 to all other nodes for a directed network with
% nonnegative arc costs.
%
% INPUTS
%
% n = number of nodes
%
% A = m x 2 matrix listing all arcs, each row [i j] represents an arc
% from node i (i = 1, ..., n) to node j (j = 1, ..., n).
%
% C = m x 1 vector listing all corresponding arc costs
%
% OUTPUTS
%
% d = n x 1 vector listing shortest path lengths, the i-th element of
% which is the shortest path length from node 1 to node i
%
% iN = n x 1 vector listing optimal predecessor nodes on the shortest
% path tree rooted at node 1. Specifically, the i-th element of iN
% represents the predecessor to node i on a shortest path from node 1 to
% node i.
bignum = 10e9; % definition of a really big number (approximating infinity)
m = length(A(:,1)); % number of arcs
% Data Structures (to be initialized below) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
nA = zeros(n,1); % column vector, i-th element of which gives the
% number of outgoing arcs for the i-th node
oA = zeros(n,m); % each row lists the nodes that can be reached
% along arcs from the corresponding node. non-zero
% entries correspond to arcs
d = zeros(n,1); % each entry stores the current distance label for
% the corresponding node
iN = zeros(n,1); % each entry stores the current best predecessor to
% the corresponding node
nT = 0; % current number of temporary nodes
T = zeros(n,1); % current temporary nodes
CC = zeros(n,n); % more convenient way of representing cost
% Initialize nA and oA %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
for k = 1:m, % index into arc list
i = A(k,1); % from node for the k-th arc
j = A(k,2); % to node for the k-th arc
nA(i) = nA(i) + 1; % increment the count of outgoing arcs from i
oA(i,nA(i)) = j; % store the corresponding destination (j) from i
CC(i,j) = C(k); % store the corresponding arc cost
end
% Initialize d %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
d = bignum*ones(n,1); % initialize all labels with large numbers...
d(1) = 0; % except for the label on s (node 1)
% Initialize iN %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
iN = -1*ones(n,1); % "-1" signifies that initially there is no
% best way into node i...
iN(1) = 0; % except for s (node i = 1)
% Initialize nT and T %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
nT = n; % initially all nodes are "temporary"
T = [1:n]; % i.e. T = [1 2 ... n]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Start Dijkstra Iterations %%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Check for termination
while nT > 0, % while there are still temporary nodes...
% look for temporary node with smallest distance label
kbest = -1; % initilize index to "best" temp node
best = bignum; % initialize best to a large number.
for k = 1:nT, % loop through all temporary nodes
i = T(k); % i is one of the temporary nodes
if d(i) <= best, % if the label for i is best so far then...
kbest = k; % ... memorize the corresponding index into T
best = d(i); % ... memorize the corresponding best distance label
end
end % T(kbest) is the temporary node with the smallest distance label
% keep track of the temporary node with smallest distance label
i = T(kbest); % i is the temporary node with smallest distance label
% adjust nT and T (remove i from T)
if kbest == 1, % if i is the first entry of T, then
T = T(2:nT); % ... keep the last nT-1 entries
elseif kbest == nT, % if i is the last entry of T, then
T = T(1:nT-1); % ... keep the first nT-1 entries
else % otherwise
T = [T(1:kbest-1) T(kbest+1:nT)]; % drop entry in the middle
end
nT = nT-1; % decrement nT to reflect that i is removed from T
% adjust d and iN (adjust labels and best predecessors);
% ********************************************************
% ************ FILL IN YOUR CODE HERE ************
% ********************************************************
end
Explanation / Answer
Dear User, function n = squareSize(G)% Returns size n of an n by n??matrix, error if the matrix is not square.
n = size( G );
if n(1) ~= n(2)
error( 'Please give me a square matrix!' );
end
n = n(1); %Implementation of Dijkstra method using MATLAB function [Distances, elapsedTime] = Dijkstra( Matrix, startnode )
% [Distances] = Dijkstra( Matrix, startnode ) returns the distances to the
% n nodes that the matrix connects, starting from the startnode. Works on
% directed graphs as well.
n = squareSize(Matrix);
Distances = Inf*ones(1,n);
Distances(startnode) = 0;
S = ones(1,n); % S(v) becomes inf when v is permanently labeled
t = clock;
for i = 1:n
minimum = min(Distances.*S);
fixed =find(Distances.*S == minimum); % which labels become permanent
fixed =fixed(1); % not very pretty, but easy, just take the rst
S(fixed)=Inf; % make this one permanent
Outgoing =find(Matrix(xed, :)); % determine non??zero outgoing edges
for j = Outgoing
if Distances(fixed) + Matrix(fixed,j) < Distances(j)
Distances(j) = Distances(fixed) + Matrix(fixed,j);
end
end
end
elapsedTime =etime(clock,t); I hope this will helps to you