使用圖算法解決應用問題: 設有n個城市, 編號為0 ~ n - 1, m條航線的起點和終點由用戶輸入提供. 尋找一條換乘次數最少的線路方案. 使用有向圖表示城市間的航線, 只要兩城市之間有航班, 則圖中這兩點間存在一條權為1的邊. 用Dijkstra算法實現求最少換乘次數. 在MGraph類中增加Choose函數以及Dijkstra函數即可. 實現代碼: ~~~ #include "iostream" #include "cstdio" #include "cstring" #include "algorithm" #include "queue" #include "stack" #include "cmath" #include "utility" #include "map" #include "set" #include "vector" #include "list" #include "string" using namespace std; typedef long long ll; const int MOD = 1e9 + 7; const int INF = 0x3f3f3f3f; enum ResultCode { Underflow, Duplicate, Failure, Success, NotPresent, OutOfBounds }; template <class T> class Graph { public: virtual ~Graph() {}; virtual ResultCode Insert(int u, int v, T w) = 0; virtual ResultCode Remove(int u, int v) = 0; virtual bool Exist(int u, int v) const = 0; /* data */ }; template <class T> class MGraph: public Graph<T> { public: MGraph(int mSize, const T& noedg); ~MGraph(); ResultCode Insert(int u, int v, T w); ResultCode Remove(int u, int v); bool Exist(int u, int v) const; int Choose(int *d, bool *vis); void Dijkstra(int v, int *d, int *path); int Vertices() const { return n; } void Output(); protected: T **a; T noEdge; int n, e; /* data */ }; template <class T> void MGraph<T>::Output() { for(int i = 0; i < n; ++i) { for(int j = 0; j < n; ++j) if(a[i][j] == noEdge) cout << "NE\t"; else cout << a[i][j] << "\t"; cout << endl; } cout << endl << endl << endl; } template <class T> MGraph<T>::MGraph(int mSize, const T &noedg) { n = mSize, e = 0, noEdge = noedg; a = new T *[n]; for(int i = 0; i < n; ++i) { a[i] = new T[n]; for(int j = 0; j < n; ++j) a[i][j] = noEdge; a[i][i] = 0; } } template <class T> MGraph<T>::~MGraph() { for(int i = 0; i < n; ++i) delete []a[i]; delete []a; } template <class T> bool MGraph<T>::Exist(int u, int v) const { if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v || a[u][v] == noEdge) return false; return true; } template <class T> ResultCode MGraph<T>::Insert(int u, int v, T w) { if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return Failure; if(a[u][v] != noEdge) return Duplicate; a[u][v] = w; e++; return Success; } template <class T> ResultCode MGraph<T>::Remove(int u, int v) { if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return Failure; if(a[u][v] == noEdge) return NotPresent; a[u][v] = noEdge; e--; return Success; } template <class T> int MGraph<T>::Choose(int *d, bool *vis) { int pos = -1; T m = INF; for(int i = 0; i < n; ++i) if(d[i] <= m && !vis[i]) { m = d[i]; pos = i; } return pos; } template <class T> void MGraph<T>::Dijkstra(int v, int *d, int *path) { if(v < 0 || v > n - 1) throw OutOfBounds; bool *vis = new bool[n]; for(int i = 0; i < n; ++i) { vis[i] = false; d[i] = a[v][i]; if(i != v && d[i] < INF) path[i] = v; else path[i] = -1; } vis[v] = true; d[v] = 0; for(int i = 1; i < n; ++i) { int x = Choose(d, vis); vis[x] = true; for(int j = 0; j < n; ++j) if(!vis[j] && d[x] + a[x][j] < d[j]) { d[j] = d[x] + a[x][j]; path[j] = x; } } } int main(int argc, char const *argv[]) { int n, m; cout << "請輸入城市個數:"; cin >> n; cout << "請輸入航線條數:"; cin >> m; MGraph<int> A(n, INF); int c, f; cout << "請輸入每條航線的起點和終點: " << endl; for(int i = 0; i < m; ++i) { cout << "航線" << i + 1 <<": "; cin >> c >> f; A.Insert(c, f, 1); } char s; int i = 0, j = 0; do{ int v, w; cout << "請輸入你的起點和終點:"; cin >> v >> w; while(v < 0 || w < 0 || w > n - 1 || v > n - 1) { cout << "輸入錯誤!請重新輸入:"; cin >> v >> w; } int *b = new int[n]; int *d = new int[n]; int *path = new int[n]; A.Dijkstra(v, d, path); int e = n - 1; for(int j = 0; j < n; ++j) b[j] = -2; if(w != v) { j = w; while(path[j] != -1) { b[e] = path[j]; e--; j = path[j]; } if(e == n - 1 || d[j] == INF) cout << "該路間無線路!" << endl; else { cout << "從" << v << "到" << w << "的換乘次數最小的線路方案為:"; for(int k = 0; k < n; ++k) if(b[k] != -2) cout << b[k] << ","; cout << w << endl; } } if(w == v) cout << "從" << v << "到" << w << "該路間無需乘飛機!" << endl; delete []b; delete []d; delete []path; cout << "請問是否繼續查詢路線?請輸入Y/N:"; cin >> s; while(s != 'Y' && s != 'y' && s != 'n' && s != 'N') { cout << "輸入錯誤!請重新輸入:"; cin >> s; } }while(s == 'Y' || s == 'y'); return 0; } ~~~