Chart theory algorithm

a [i, j]: = a [i, k] a [k, j];

P [I, J]: = P [k, j];

END;

END;

C. Dijkstra Algorithm:

VAR

A: array [1..maxn, 1..maxn] of integer;

B, pre: array [1..maxn] of integer; {pre [i] refers to the front disseval point of i on the shortest path.

Mark: array [1..maxn] of boolean; procedure dijkstra (v0: integer);

Begin

Fillchar (Mark, SizeOf (Mark), False;

For i: = 1 to n DO

Begin

D [i]: = a [v0, i];

IF D [i] <> 0 THEN

Pre [I]: = V0

Else pre [I]: = 0;

END;

Mark [v0]: = true;

Repeat {Add a nearest node close to 1 episodes per loop and adjust the parameters of other nodes}

MIN: = Maxint; u: = 0; {u Record from 1 episode nearest node}

For i: = 1 to n DO if (Not Mark [i]) and (d [i]

Begin

u: = i;

Min: = d [i];

END;

IF u <> 0 THEN

Begin

Mark [u]: = true;

For i: = 1 to n DO

IF (Not Mark [I]) and (a [u, i] d [u]

Begin

D [i]: = a [u, i] d [u];

Pre [i]: = u;

END;

END;

Until u = 0;

END;

3. Calculate the pass closure

PROCEDURE longlink;

Var T: array [1..maxn, 1..maxn] of boolean;

Beginfillchar (t, sizeof (t), false; fork: = 1 to n DO

For i: = 1 to n DO

For j: = 1 to n DO

T [I, J]: = T [i, j] or (t [i, k] and t [k, j]);

END;

4. Non-map connected component

A. Depth priority

Procedure DFS (Now, Color: Integer);

Begin

For i: = 1 to n DO

IF a [now, i] and c [i] = 0 THEN

Begin

{Dyeing node i}

C [I]: = Color;

DFS (I, Color);

END;

END;

B width priority (seed staining)

5. Key path a few definitions: vertex 1 is the source point, n is a combo.

a. The earliest time VE [J], VE [J] = Max {VE [J] W [i, J]}, B, where VE (1) = 0;

b. Top events Time VL [J], VL [J] = min {VL [J] - W [i, J]}, where VL (n) = VE (N);

c. The earliest start time of the event EE [i], if the side i is represented by , then EE [i] = ve [j];

d. Lateurning Time EL [i], if the side i is indicated by , EL [I] = VL [K] - W [J, K];

If EE [J] = EL [J], the activity J is a critical activity, and the path consists of key activities is a critical path. Solution:

a. From the source point to TOPSORT, determine if there is loop and calculate the VE;

b. From the exchange points to Tops, seeking VL;

EE and EL;

6. Topological order finding points 0 points, deleting all sides connected to them, continuously repeating this process. example

Look for a number, including any of the consecutive P items, and the sum of the sum of any Q items, if there is no existence, the NO is output.

7. Turning road problem Euler loop (DFS)

Definition: Only one loop through each side of the figure. (Mon for conditions: Tiantian and not quenching) Hamilton

Loop definition: The loop is only once through each vertex. A painting feature condition: Figure connected and the number of odds is 0

Or 2.

9. Is there a negative loop in the figure, Bellman - Ford algorithm x [i], y [i],

T [i] indicates the starting point, end point and right of the first side of the first section. A total of n nodes and M strips.

Procedure Bellman-ford

Begin

For i: = 0 to n - 1 do

D [I]: = Infinitive;

D [0]: = 0;

For i: = 1 to n - 1 do

For j: = 1 to m do {enumeration every side}

IF D [X [J]] T [J] D [y [j]] THEN

D [Y [J]]: = D [x [j]] t [j];

For i: = 1 to m DO

IF D [X [J]] T [J] D [y [j]] THEN

Return False

Else Return True;

END;

10. Nth shortest path problem *

Second shortest path: Each side of the shortest path is heated, each time you delete one, then ask the shortest path of the new map, take the shortest one of these paths to the second shortest path.

* Similarly, the minimum path can be solved on the basis of solving the Nth-1 shortest path.