使用图算法解决应用问题: 设有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; }

顶 1 踩 0

我的同类文章

查看评论

* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场