Algorithm serial (5) - Dynamic Planning AllPath

1. Problem Description: Set g = (v, e) is a directorial view with n nodes. Also set is G is a cost adjacent matrix, where C (i, i) = 0, 1 <= i <= n; When belongs to E (g), C (i, j) means side < The cost of i, j>; when i is not equal to J and do not belong to E (g), C (i, j) is equal to infinity (represented by a large number). Ask the shortest path between each pair of nodes.

2. Design ideas and analysis: Basic ideas: Which node that first decisive is the middle junction K on the path, then go to seek from i to k and by K to J. The shortest path, record the intermediate node K. If node i, the minimum path can be obtained without having to pass the other nodes, and the cost of the itself is reserved and the intermediate node is not recorded.

(There is a problem with the traversal of this design, and you can't traverse the path of 2 nodes.) Has not been revised.)

#include int const m = 4;

Struct node {int flag [m]; // is used to record the node float cost to each pair of nodes to pass; // to record the path cost} of the node to the node;

Void All_Paths (Node Cost [M] [M], Node A [M] [M], INT N) {INT I, J, K; // Copying the adjacent matrix for (i = 0; i

// * Use the dynamic planned part, the core algorithm * // for (k = 0; k (a [i] [k] .cost a [k ] [j] .cost)) {a [i] [j] .cost = (a [i] [k] .cost a [k] [j] .cost); a [i] [j] .flag [k] = k 1; // Record the node number to pass by ELSE A [I] [J] .cost = a [i] [j] .cost;}}

For (i = 0; i ; For (k = 0; k ";} Cout << j 1 << ENDL << Endl;}} else cout << endl;}}}

Void main () {cout << "| -------- The shortest path between each pair of nodes ------- | << Endl; cout <<" | --- oer by ZhanjianTao (028054115) --- | "<< endl; cout <<" | -------------------------------------------------------------------------------------------------------------------------------------------- ----- | << endl << Endl; cout << "Note: Please do not input costs greater than 100, itself is in its own input 0, input 100 means" << end1; int i, j, n , K; Struct node cost [m] [m]; struct node a [m] [m]; while (k) {cout << "Non-point total number is three, please construct this picture." << Endl < > n; n = 3; for (i = 0; i > COST [I] [J] .cost;

All_paths (COST, A, N); COUT << "Press <1> to Run Again" << Endl; Cout << "Press <0> to exit" << Endl; CIN >> K;}}