本帖最后由 2425 于 2016-8-20 19:18 编辑
算法方面的解释：
正如主楼里面我提到的技术实现分析所说，目前航路计算使用的是优先队列优化的迪杰斯特拉算法。这是图论中非常基础的一个单源最短路算法，实现起来也比较简单所以在分析中没有详细解释。
不知你程序设计水平如何，但我还是给出一段代码。下面给出的是根据《挑战程序设计竞赛》（秋叶拓哉 ，岩田阳一，北川宜稔）中Dijkstra相关示例修改而来的说明代码：
- #include <queue>
- #include <vector>
- #include <utility>
- struct edge{
- int to;
- int cost;
- };
- typedef std::pair<int, int> P;//first 最短距离, second 顶点编号
- int v;
- std::vector<edge> g[max_v];
- int d[max_v];
- void Dijkstra(int s)
- {
- std::priority_queue<P, std::vector<P>, std::greater<P> > que;
- for(int i = 0; i != v; ++i)
- d[i] = INF;
- d[s] = 0;
- que.push(P(0, s));
- while(!que.empty()){
- P p = que.top();
- que.pop();
- int v = p.second;
- if(d[v] < p.first)
- continue;
- for(unsigned int i = 0; i != g[v].size(); ++i){
- edge e = g[v][i];
- if(d[e.to] > d[v] + e.cost){
- d[e.to] = d[v] + e.cost;
- que.push(P(d[e.to], e.to));
- }
- }
- }
- }
就航路计算来说：
我们将机场、航路上的点均作为图中的顶点看待，由导航数据可以建立一个有向图。
数组d中存放的是计算过程中由源点到达各个顶点的距离，首先将它们都初始化为无穷大，并将源点放入优先队列中。
不断地从优先队列中取出顶点-最短距离对并判断当前是否存在更优解，若不存在，遍历该顶点的邻接表中所有顶点，存在更优解情况时进行更新并将其加入优先队列。优先队列优化的迪杰斯特拉算法复杂度为O(E logV)。
对于寻找航路的情况，在每次更新更优解时，维护一个pre数组，更新到达该顶点的前一个顶点。Dijkstra运行完后，从终点出发不断地根据pre数组存储的前一个顶点编号回溯一直到达起点，将得到的顶点全部反向就得到了正向航路。
具体的实现，都在Finder.cpp里，可以到GitHub上查看。
|
[复制链接]
雷达卡
发表于 2016-8-20 14:37:41
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
发表于 2016-8-20 14:39:00
楼主
