DS图-最短路径

#include <iostream> #include <climits> using namespace std; const int MaxLen = 20; const int MaxDist = 9999; class Map { private: int Matrix[MaxLen][MaxLen]; int Vexnum; public: void SetMatrix(int vnum, int mx[MaxLen][MaxLen]); void ShortPath(int v0); }; void Map::SetMatrix(int vnum, int mx[MaxLen][MaxLen]) { int i, j; Vexnum = vnum; for (i = 0; i < MaxLen; i++) for (j = 0; j < MaxLen; j++) Matrix[i][j] =MaxDist; for (i = 0; i < Vexnum; i++) for (j = 0; j < Vexnum; j++) if (mx[i][j]) Matrix[i][j] = mx[i][j]; } void Map::ShortPath(int v0) { int *dist = new int[Vexnum]; bool *final = new bool[Vexnum]; int len[MaxLen]; int path[MaxLen][MaxLen]; for (int i = 0; i < Vexnum; i++) { final[i] = false; dist[i] = Matrix[v0][i]; } for (int i = 0; i < MaxLen; i++) for (int j = 0; j < MaxLen; j++) path[i][j] = -1; for (int i = 0; i < MaxLen; i++) { path[i][0] = v0; path[i][1] = i; len[i] = 2; } dist[v0] = 0; final[v0] = true; for (int i = 0; i < Vexnum; i++) { if (i == v0) continue; int min = MaxDist; int v; for (int j = 0; j < Vexnum; j++) if (final[j] == false && min > dist[j]) { min = dist[j]; v = j; } final[v] = true; for (int s = 0; s < Vexnum; s++) if (!final[s] && (min + Matrix[v][s]) < dist[s]) { dist[s] = min + Matrix[v][s]; int k; for (k = 0; k < len[v]; k++) path[s][k] = path[v][k]; path[s][k] = s; len[s] = len[v] + 1; } } for (int v = 0; v < Vexnum; v++) if (v != v0) { cout << v0 << '-' << v << '-' << dist[v] << "----["; for (int l = 0; l < len[v]; l++) cout << path[v][l] << ' '; cout << ']' << endl; } delete[]dist; delete[]final; } int main() { int i, j, k, t; int vnum, v0; int mx[MaxLen][MaxLen]; Map myMap; cin >> t; for (k = 0; k < t; k++) { for (i = 0; i < MaxLen; i++) for (j=0;j<MaxLen;j++) mx[k][i] = 0; cin >> vnum; for (i = 0; i < vnum; i++) for (j = 0; j < vnum; j++) cin >> mx[i][j]; myMap.SetMatrix(vnum, mx); cin >> v0; myMap.ShortPath(v0); } system("pause"); return 0; } /* *******最短路劲******* 样例输入 1 5 0 5 0 7 15 0 0 5 0 0 0 0 0 0 1 0 0 2 0 0 0 0 0 0 0 0 ******************** 样例输出 ：0-每一结点-最短路径值----[路径所经过的结点] 0-1-5----[0 1 ] 0-2-9----[0 3 2 ] 0-3-7----[0 3 ] 0-4-10----[0 3 2 4 ] */ //ShortPath的另一种实现 void Map::ShortPath(int v0) { int *dist = new int[Vexnum]; bool *final = new bool[Vexnum]; int len[MaxLen]; int path[MaxLen][MaxLen]; for (int i = 0; i < Vexnum; i++) { final[i] = false; dist[i] = Matrix[v0][i]; } for (int i = 0; i < MaxLen; i++) for (int j = 0; j < MaxLen; j++) path[i][j] = -1; for (int i = 0; i < MaxLen; i++) { path[i][0] = v0; if (i==v0) path[i][1] = i; //path[i][1] = i; if (i!=v0) len[i] = 1; else len[i] = 2; } dist[v0] = 0; final[v0] = true; int prev = v0; for (int i = 0; i < Vexnum; i++) { if (i == v0) continue; int min = MaxDist; int v; for (int j = 0; j < Vexnum; j++) if (final[j] == false && min > dist[j]) { min = dist[j]; v = j; } if (min < MaxDist) { int k; for (k = prev != v0 ? 0 : 1; k < len[prev]; k++) { if (prev == v0) path[v][k - 1] = path[prev][k]; else path[v][k] = path[prev][k]; } if (prev == v0) path[v][k - 1] = v; else path[v][k] = v; if (prev == v0) len[v] = len[prev]; else len[v] = len[prev] + 1; prev = v; } final[v] = true; for (int s = 0; s < Vexnum; s++) if (!final[s] && (min + Matrix[v][s]) < dist[s]) { dist[s] = min + Matrix[v][s]; // int k; // for (k = 0; k < len[v]; k++) // path[s][k] = path[v][k]; // path[s][k] = s; // len[s] = len[v] + 1; } } for (int v = 0; v < Vexnum; v++) if (v != v0) { cout << v0 << '-' << v << '-' << dist[v] << "----["; for (int l = 0; l < len[v]; l++) cout << path[v][l] << ' '; cout << ']' << endl; } delete[]dist; delete[]final; }