Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

The second part – code function realization.

First give a figure and a table.

One of the key steps is to find small paths. We can create an array D [5] to store the distance from S to each point. In addition, we can find the minimum path of the new node by constantly updating the data in D.

Array d[5] is initialized

We initialize the array D so that d[s] is equal to 0 and the other values are equal to infinity, which we set to 999.

for(int i=0; i<5; i++) d[i]=999;
d[s]=0;
Copy the code

D [5] Data update

Since we use D [5] to store the length of the path, we change the data in D every time we find a shorter path.

We deal with the edge of s and we identify y

First of all, we start at s and combine the two dimensional array to find that S has two paths,s-> t and S ->z.

Let’s compare. The original value at t and z was 999, so I’m going to replace 999.

The s point in the red circle in the figure represents the current processing point, and the green area represents the value of s->t and S -> Y.

We deal with the edges of y and we identify t

In the figure,s circled in orange represents the identified point, Y circled in red represents the current processing point, and green represents the value of Y ->x and Y -> Z. Note that the value represented here is not just y-> X or Y -> X, but the value of y itself, which really means s-> Y -> X and S -> Y -> Z. Where the blue area represents the value of the replacement, to find a shorter path.

Let’s find the shortest node and let’s make sure.

We deal with the edge of t and we identify z

Here we compare t->y to 7, which is greater than 4, so we don’t change it

We deal with the edges of z and we identify x

code

int x=s;
for(int i=0; i<4; i++){for(int j=0; j<5; j++){if(g[x][j]+d[x]<d[j]){ d[j]=g[x][j]+d[x]; }}}Copy the code