Basic algorithm - chart

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]

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]

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;

Begin

Fillchar (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 DOIF A [now, i] and c [i] = 0 dam {Non-point i dye}

C [I]: = Color;

DFS (I, Color);

END;

END;

B width priority (seed staining)

5. Critical Path

Several definitions: The vertex 1 is the source point, n is a combo.

a. Vertical event time occurrence time VE [J], VE [J] = Max {VE [J] W [i, j]}, where VE (1) = 0

;

b. Top event Time Time VL [J], VL [J] = min {VL [J] - W [i, j]}, where VL (n) = V

e (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. Topology sort

The point of finding 0 is 0, and the other side of which is connected is deleted, and the process is repeated.

For example, the sum of any continuous P items is positive, any Q item and the negative, if there is no existence, output NO.

7. Logging problem

Euler loop (DFS)

Definition: Only one loop through each side of the figure. (Mon for conditions: Figure is connected with and not quenching)

Hamilton loop

Definition: The loop is only once through each vertex.

A brush

MA. Active condition: Figure Tong Tong and the number of odds are 0 or 2.

9. Is there a negative circuit Bellman-Ford algorithm in the figure?

X [i], y [i], t [i] indicates the starting point, end point, and weight of the first edge of the clip. 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] THEN D [Y [J]: = D [x [j]] t [j];

For i: = 1 to m DO

IF D [X [J]] T [J] D [Y [J]. Return False Else Return True;

END;

10. Nth shortest path problem

* Second shortest path: Each side of the shortest path, each delete one, then ask the shortest path of the new map, take

The shortest one in these paths is the second shortest path.

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