Who can give an example of using Pascal language and Dijkstra algorithm to find the shortest path of a single source and explain it?

[Problem analysis]

For a graph with n vertices and e edges, the shortest path from one vertex Vi to any other vertex Vj may be the edge (Vi, Vj) between them, or the path formed by k intermediate vertices and k+ 1 edge (1≤k≤n-2). The idea of Dijkstra algorithm to solve this problem is given below.

Let graph G be stored in GA in the form of adjacency matrix, where GA[i, j]=maxint indicates that Vi and Vj are irrelevant, otherwise it is a weight (real number greater than 0). Let set S be used to store the terminal number of the shortest path. The beginning S=[Vi] indicates that there are only source points. After that, one endpoint Vj is found at a time, which will be added to the collection as a newly considered intermediate vertex. Let the array dist [1...n] be used to store the shortest path currently obtained. If Vi is related to the beginning of Vj, dist[j] is equal to weight, otherwise it is equal to maxint. In the future, dist[j] may become smaller and smaller with more and more newly considered intermediate vertices. Set the array path [1...n] corresponding to dist to store the edge of the current shortest path. At first, it was the edge from Vi to Vj, and it was empty without edge.

When executing, the element with the smallest value (assumed as dist[m]) is found out from the elements of dist array corresponding to vertices other than S, which is the shortest path length from the source point Vi to the destination Vm, and the sequence of vertices or edges in the corresponding path [m] is the shortest path. Then, the Vm is merged into the set S, and then the Vm is taken as the middle vertex of the new consideration. For each vertex Vj except s, compare the size of dist [j] of dist[m]+GA[m, j]. If the former is smaller, it means that a better scheme can be obtained by adding a new intermediate vertex, that is, a shorter path [j] can be obtained, so it is used instead of dist[j], and Vj or edge is also used. Repeat the above process for n-2 times, and you can get the length of the longest path from the source point to the other endpoints in the dist array, and the corresponding longest path is stored in the corresponding path array.

The concrete framework of Dijkstra algorithm is given below (note: for the convenience of implementation, a one-dimensional array S [1...n] is used to store the endpoint set of the shortest path, that is, if s[j]=0 indicates that the vertex Vj is not in the set, on the contrary, s[j]= 1 indicates that the vertex Vj is in the set).

Program Dijkstra(GA, dist, path, I);

{means to find the shortest path from Vi to other vertices in graph G, where GA is the adjacency matrix of graph G, dist and Path are variable parameters,

In which the basic type of the path is set}

begin

For j:= 1 to n, start {initialization}

If j<& gtI and then s [j]: = 0 else s [j]: =1;

dist[j]:=GA[i，j]；

if dist[j]& lt； Maxint and then path [j]: = [I]+[j] else path [j]: = [];

End;

For k:= 1 to n-2 Do

begin

w:= maxint； m:= I；

For j:= 1 to n Do {the kth endpoint VM is found}

If (s[j]=0) and (dist [j] <; W) then start m: = j; w:= dist[j]； End;

If m<& gtI then s[m]:= 1 else exits;

{If the condition holds, please add the virtual machine to s,

Otherwise, exit the loop, because the shortest path length of the remaining endpoints is maxint, so there is no need to calculate again.

For j:= 1 to n Do {make necessary modifications to better elements with s[j]=0}

If (s[j]=0) and (dist[m]+GA[m，j]& lt； dist[j])

Then Begin Dist[j]:=dist[m]+GA[m, j]; path[j]:= path[m]+[j]； End;

End;

(1) The shortest path from one vertex to other vertices.

For a graph with n vertices and e edges, the shortest path from one vertex vi to any other vertex vj may be the edge (vi, vj) between them, or the path formed by k intermediate points and k+ 1 edge (1≤k ≤n-2).

Firstly, the algorithm thought of Dijkstra is analyzed.

Let graph G be stored in GA in the form of adjacency matrix, where GA[I, j]=maxint indicates that vi and vj are irrelevant, otherwise it is a weight (real number greater than 0). Let set S be used to store and save the terminal number of the shortest path. At the beginning, S=[vi] means that there is only the source point, and every time a terminal vj is found in the future, it will be added to the set as a newly considered intermediate vertex. Let the array dist [1...n] be used to store the shortest path currently obtained. Dist[j] is equal to weight if there is a relationship between vi and vj, otherwise it is equal to maxint. In the future, dist[j] may become smaller and smaller with more and more newly considered intermediate vertices. Set the array path [1...n] corresponding to dist to store the edge of the current shortest path. Initially, if there is no edge, the edge from vi to vj will be empty.

When executing, the element with the smallest value (assumed as dist[m]) is found out from the elements of dist array corresponding to vertices other than S, which is the shortest path length from the source point vi to the destination vm, and the sequence of vertices or edges in the corresponding path [m] is the shortest path. Then, the vm is merged into the set S, and then the vm is taken as the middle vertex of the new consideration. For each vertex vj except s, compare the sizes of dist[m]+GA[i, j] and dist[j]. If the former is smaller, it means that a better scheme can be obtained by adding a new intermediate vertex, that is, a shorter path [j] can be obtained, so it is used instead of dist[j], and vj or edge is also used. By repeating the above process for n-2 times, the shortest path length from the source point to the other endpoints in the dist array can be obtained, and the corresponding shortest path is stored in the corresponding path array.

For the convenience of implementation, the one-dimensional array S [1...n] is used to save the endpoint set of the shortest path instead of the set S, that is, if s[j]=0 indicates that the vertex vj is not in the set, on the contrary, s[j] indicates that the vertex vj is already in the set).

Dijkstra program (GA, dist path, i)

begin

Start with j:= 1 to n.

If j<& gtI and then s [j]: = 0; {j is not in the set} else s [j]: =1; {j is in the set};

dist[j]:=GA[I，J]；

IF dist[j]& lt； Maxint {maxint is an assumed large enough number}

Then the path [j]:=[I]+[j]

Else path [j]: = [];

End;

For k:= 1 to n-1dobeginw: = maxint; m:= I；

For j:= 1 to n do{ the kth endpoint VM is found}

If (s[j]=0) and (dist [j] <; W) then start m: = j; w:= dist[j]； End;