dijistra
const int N = 10;
int used[N]; //用没有用过
int path[N]; //i的前一个节点
int dist[N]; //最短路径
void f(Graph G, int v) {
for (int i = 0; i < N; i++) {
used[i] = 0;
dist[i] = G.edge[v][i];
if (G.edge[v][i] < Max) path[i] = v;
else path[i] = -1;
}
used[v] = 1;
path[v] = -1;
for (int i = 0; i < N; i++) {
int _min = Max;
int u;
for (int j = 0; j < N; i++) {
if (used[j] == 0 && dist[j] < _min) {
_min = dist[j];
u = j;
}
used[u] = 1;
}
for (int j = 0; j < N; j++) {
if (used[j] == 0 && dist[u] + G.edge[u][j] < dist[j]) {
dist[j] = dist[u] + G.edge[u][j];
path[j] = u; //u->j j的前一个节点为u
}
}
}
}
floyd
const int N = 10;
int A[N][N];
void floyd(int n, Graph[N][N], int path[N][N]) {
int i, j, v;
for (int i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
A[i][j] = Graph[i][j];
path[i][j] = -1;
}
}
for (v = 0; v < n; v++) { //v为中间节点
for (i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (A[i][j] > A[i][v] + A[v][j]) {
A[i][j] = A[i][v] + A[v][j];
path[i][j] = v;
}
}
}
}
}
void printPath(int u, int v, int path[N][N]) {
if (path[u][v] == -1) {
cout << "结果"; //一段的结果;
}
else {
int mid = path[u][v];
printPath(u, mid, path);
printPath(mid, v, path);
}
}