function [ParentList DiscoveryList DistanceList] = Dijkstra(EdgeListG, Weights, startV, n)
%  [ParentList DiscoveryList DistanceList] = Dijkstra(EdgeListG, Weights, startV, n)

%We initialize the tree growing edge lists:
EdgeListT = []; %initially T consists of just the starting vertex startV (no edges)
%The boundary edges are all edges adjacent to startV
EdgeListGEndpts = EdgeListG(:,1:2); %indices have been removed (i.e., the third column was truncated)
[a b] = find(EdgeListGEndpts == startV); 
BdyEdges = EdgeListG(a,:);
%The boundary edges are the only edges that are initially "used"
UnusedEdges = setdiff(EdgeListG, BdyEdges, 'rows');


DiscoveryList = [startV];
%Initially, only the distance from the root to itself is known = 0.
DistanceList = [0];
ParentList = zeros(1,n);
%A zero entry in ParentList will mean the vertex has no parent "NULL"
%In the initial tree T = [startV], no vertex has a parent (and the root
%startV never will)
CurrDist = Inf*ones(1,n);
CurrDist(startV)= 0;

%Before entering into the while loop, we do the first iteration separately
%because initially EdgeListT is empty (so does not have startV)
%First Edge Selection Step (Dijkstra)
%Need to find a lightest boundary edge
[lightest ind] = min(Weights(BdyEdges(:,3)));
e = BdyEdges(ind,:); %third entry is the index of edge w.r.t. EdgeListG
if e(1) == startV;
    nonTreeEndpt = e(2);
else
   nonTreeEndpt = e(1);
end
DiscoveryList = [DiscoveryList nonTreeEndpt];
ParentList(nonTreeEndpt) = startV;
CurrDist(nonTreeEndpt) = Weights(BdyEdges(ind,3));
DistanceList = [DistanceList CurrDist(nonTreeEndpt)];
%%%Pasted from BdyEdgesUpdateInd program
%We need to delete any edge of BdyEdges that has nonTreeEndpt
%as one of its endpoints.
BdyEdgesEndpts = BdyEdges(:,1:2);
[a b] = find(BdyEdgesEndpts == nonTreeEndpt);
BdyEdges(a,:) = []; BdyEdgesEndpts(a,:) = [];
%Next, we find the unused edges that are incident to nonTreeEndpt.  The
%vector a below gives their row indices in UnusedEdges, and the vector b
%gives the columnn index(1 or 2) in which nonTreeEndpt occurs.
UnusedEdgesEndpts = UnusedEdges(:,1:2);
[a b] = find(nonTreeEndpt==UnusedEdgesEndpts);
%We add these edges to BdyEdges
BdyEdges = [BdyEdges; UnusedEdges(a,:)];
BdyEdgesEndpts = BdyEdges(:,1:2);
%and delete them from UnusedEdges
UnusedEdges(a,:)=[];
UnusedEdgesEndpts = UnusedEdges(:,1:2);
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
EdgeListT = [EdgeListT; e];
EdgeListTEndpts= EdgeListT(:,1:2);

while ~isempty(BdyEdges)
    %Next Edge Selection Step (Dijkstra)
    %Need to find a boundary edge such that when its weight is added to
    %CurrDist of its tree endpt (=the shortest distance to root) it is a
    %minimum
    CurrDistTemp = CurrDist;
    Best = [Inf 0 0 0]; %will store min non tree endpt new distance (first component), and 
    %non tree endpt (second component intialized to 0), tree endpt (third component), 
    %and index of corresponding bdy edge (forth component)  
    for i = 1:n
            if ismember(i,EdgeListTEndpts) %i is a tree vertex
            [a b] = find(i == BdyEdgesEndpts); %a = indices of bdy edges incident to i
            for j = 1:length(a)
                if BdyEdges(a(j),1)==i 
                    nonTreeEndpt = BdyEdges(a(j),2);
                else
                    nonTreeEndpt = BdyEdges(a(j),1);
                end
                if CurrDist(i) + Weights(BdyEdges(a(j),3)) < Best(1) %nonTreeEndpt is candidate 
                                                    %for next discovery vertex
                    Best = [CurrDist(i) + Weights(BdyEdges(a(j),3))  nonTreeEndpt i BdyEdges(a(j),3)]
                end
            end
            end
    end
    
    DiscoveryList = [DiscoveryList Best(2)];
    ParentList(Best(2)) = Best(3);
    CurrDist(Best(2)) = Best(1);
    DistanceList = [DistanceList Best(1)];
    [BdyEdges UnusedEdges]= BdyEdgesUpdateInd(EdgeListT, BdyEdges, [Best(2) Best(3)], UnusedEdges);
    BdyEdgesEndpts = BdyEdges(:,1:2);
    UnusedEdgesEndpts = UnusedEdges(:,1:2);
    EdgeListT = [EdgeListT; [Best(2:4)]];
    EdgeListTEndpts= EdgeListT(:,1:2);
end
%Finally we format the outputs
ParentList2 = zeros(2,n);
ParentList2(1,:) = 1:n;
ParentList2(2,:) = ParentList;
ParentList = ParentList2';