Dijkstra算法和A算法的比较
1.性能：
Dijkstra算法的实质是广度优先搜索，是一种发散式的搜索，空间和时间复杂度都很高。
而A算法可以通过A算法的参数来控制路径更倾向于向终点方向探索，因此A算法性能优于Dijkstra算法。

2.品质：
Dijkstra算法因为使用的是实际的cost值并且每一次新一轮的遍历永远是距离起始点最优的位置，因此总能找到最优解。
A算法寻路过程中使用了估算值，A算法得到的路径不一定最优。

1.全路径探索时使用双向Dijkstra算法，auto-reroute时使用单向Dijkstra算法。
2.长路径(超过100km)时使用A*算法，并通过增加正反向算路相遇次数来保证取得最优解。

Dijkstra

从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。
以起始点为中心向外层层扩展，直到扩展到终点为止。
引入两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。
1.初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为起点s到该顶点的距离。[例如，U中顶点v的距离为(s,v)的长度，若s和v不相邻，则v的距离为∞]
2.从U中选出距离最短的顶点k，并将顶点k加入到S中；同时，从U中移除顶点k
3.更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(s,v)的距离可能大于(s,k)+(k,v)的距离
4.重复步骤(2)和(3)，直到遍历完所有顶点

/*
测试数据 6个顶点的邻接矩阵 其中 数字1000000代表无穷大
6
1000000 1000000 10 100000 30 100
1000000 1000000 5 1000000 1000000 1000000
1000000 1000000 1000000 50 1000000 1000000
1000000 1000000 1000000 1000000 1000000 10
1000000 1000000 1000000 20 1000000 60
1000000 1000000 1000000 1000000 1000000 1000000
结果：
D[0]   D[1]   D[2]   D[3]   D[4]   D[5]
0   1000000   10     50     30     60
*/
#include <stdio.h>

#define POINT_NUM 6
#define MAX 1000000

//邻接矩阵
int arcs[POINT_NUM][POINT_NUM] = { 0, 1000000, 10, 100000, 30, 100,
1000000, 0, 5, 1000000, 1000000, 1000000,
1000000, 1000000, 0, 50, 1000000, 1000000,
1000000, 1000000, 1000000, 0, 1000000, 10,
1000000, 1000000, 1000000, 20, 0, 60,
1000000, 1000000, 1000000, 1000000, 1000000, 0 };

//用Dijkstra算法求有向网的v0顶点到其余顶点v的 最短路径P[v]及带权长度D[v]
int D[POINT_NUM];//保存最短路径长度
int P[POINT_NUM][POINT_NUM];//路径
int final[POINT_NUM];//若final[i] = 1则说明 顶点vi已在集合S中

void ShortestPath_DIJ()
{
    int v0 = 0;//源点
    int v, w;
    for (v = 0; v < POINT_NUM; v++) //初始化
    {
        final[v] = 0;
        D[v] = arcs[v0][v];
        for (w = 0; w < POINT_NUM; w++)
            P[v][w] = 0;//设空路径
        if (D[v] < MAX){
            P[v][v0] = 1;
            P[v][v] = 1;
        }
    }

    final[v0] = 1; //初始化 v0顶点属于集合S
    //开始主循环 每次求得v0到第几个顶点Vi的最短路径 并把Vi加到集合S中
    for (int i = 1; i < POINT_NUM; i++)//除起点外的POINT_NUM-1个顶点
    {
        int min = MAX;
        //选点 找到当前离V0最近的点 依次为10 30 100
        for (w = 0; w < POINT_NUM; w++)
        {
            if (!final[w])
                if (D[w] < min) { v = w; min = D[w]; }
        }
        final[v] = 1; //选出该点后加入到合集S中
        for (w = 0; w < POINT_NUM; w++)//更新当前最短路径和距离
        {
            //v为当前刚选入集合S中的点，以点V为中间点 
            //比如加进点 3 则若要考察 D[5] 是否要更新 就 判断 D(v0-v3) + D(v3-v5) 的和是否小于D[5]
            if (!final[w] && (min + arcs[v][w]<D[w]))
            {
                D[w] = min + arcs[v][w];
                // p[w] = p[v];
                P[w][w] = 1; //p[w] = p[v] +　[w]
            }
        }
    }
}

int main()
{
    ShortestPath_DIJ();
    for (int i = 0; i < POINT_NUM; i++)
        printf("D[%d] = %d\n", i, D[i]);

    return 0;
}

A*（A-Star)

一种静态路网中求解最短路径最有效的直接搜索方法。
A关注点到点的最短路径，A 除了考虑当前点离起始点的距离外，还考虑了当前点离目标点的距离。也就是说，A比Dijkstra算法多了一个估算函数，若估算函数为0，A算法也就退化为Dijkstra算法。

曼哈顿距离：两点在南北方向上的距离加上在东西方向上的距离。
欧式距离：两点间的直线距离。
RDTEG中A*的估算值使用的是欧式距离。


横向和纵向的移动代价为 10 ，对角线的移动代价为 14 。因为实际的对角移动距离是 2 的平方根近似与1.4倍的横向或纵向移动代价。
F = G + H
G表示从当前点离起始点的距离，H表示从当前点离目标点的距离（估算）。

1. 从起点 A 开始，并把它就加入到一个由方格组成的 open list 中。现在 open list 里只有起点 A ，后面会慢慢加入更多的项。 Open list 里的格子都是下一步可以到达的，基本上 open list 是一个待检查的方格列表。
2. 查看与起点 A 相邻的方格，把可到达的方格也加入到 open list 中。把起点 A 设置为这些方格的父亲。当我们在追踪路径时，这些父节点的内容是很重要的。因为它记录了从起点到该点的最短路径上经过的最后一个节点。
3. 把 A 从 open list 中移除，加入到 close list中， close list 中的每个方格现在不需要再关注。
4. 从 open list 中选最小 F 值的方格，重复23步骤。

反复遍历 open list ，选择 F 值最小的方格，产生新的可供选择的方格，直到找到终点方格。