那天师兄给面试，面到一道图算法题目，求图中两个点的前K短路径。当时觉得用Dijkstra+heap应该可以，不过也没想清楚。以前看到过这个，那时还没怎么仔细看图算法所以丢一边了， 今天好好看了一下。简单一点的解法是用Dijkstra+Astar。典型的题目就是POJ 2449。   

A* 算法

再谈A*算法。A*算法中的评估函数为f(N)=cost(N)+h*(N)。其中cost(N)为从源点到N点的距离，h*(N)为N点到终点的的一个评估路径长度，设h(N)为实际N点到终点的路径长度。只要满足条件： h*(N)<=h(N)，那么用这个评估函数找到最短路径。具体证明看这篇论文A Formal Basis for the Heuristic Determination of Minimum Cost Paths。 其优势在于在选择每个路径 上的点的时候给予了h(N)这个启发，在搜索空间中尽量选择可能最有可能产生最优解的下一个状态，使得搜索的时间都相应地减少。A*算法的思想也是贪心 的，Dijkstra是A*的一个特例，当h*(N)=0时，A*就退化成了Dijkstra算法，那么就是盲目的扩展当前最短路径了。    来个例子，下面这是一个城市的公路图网，一共有18263个点，23874条边，视为无向图。我们知道起点和终点的坐标，现在我们要求某两点之间的最短路径。   

1.  用Dijkstra算法来，其中白色的点表示搜索过程中访问了的点。可以看出Dijkstra算法有点像BFS向周围扩展,做了很多无用的搜索。当然这与图的形状也有一定关系。   

[Dijkstra 访问18191个点]

 

2.  用A*算法，设S为起点，T为终点，启发函数为F(N)=Path_Dist(S->N)+Dist(N->T)。在搜索过程中Path_Dist一直维持着S->N的路径长度，Disk(N->T)的计算可以有多钟选择，这里我选择 Dist(N->T)=sqrt(|Xn-Xt|*|Xn-Xt|+|Yn-Yt|*|Yn-Yt|),这个为两点之间的理论最短路径，肯定是满足条件h*(N) <= h(N)的，那么能得到最优解。可以看到搜索偏向于目标点的方向。   

[A* 两点之间距离为评估函数 访问4398个点]

 

3. 另外(x+y)/2 <= sqrt(x^2+y^2)，所以也可以选择(|Xn-Xt|+|Yn-Yt|)/2作为启发函数。但为了节省这个sqrt的操作，代价就是访问了更多的点。   

[A* (x+y)/2作为启发函数 访问14374个点]

 

4. 可以做得更好，修改启发函数。Dist(N->T)=|Xn-Xt|+|Yn-Yt|,这为曼哈顿函数，这样就不满足条件h*(N)<=h(N)了。所以得不到最优解，但是速度上会快很多，搜索的点也会减少很多。   

[A* 曼哈顿距离作为启发函数 访问296个点]

  大概能得到一个规律，搜索效率依赖于h*(N)的启发作用，当h*(N) <= h(N)时候，我们能得到最优解，用第二种启发函数能也满足最优解的条件，但是因为启发用少了所以访问了更多的点。当h*(N)>h(N)时，得到的可能是比较优的解(非最短路径)，可以认为因为得到的启发更多(多到超出了得到最优解的条件限制)，所以能取得更快的效率。这又是一个普遍的问题，在速度、精确度两者之间经常会只能二选一，对于不同的应用从中作出折中。上面那篇论文证明了，对于刚才举例的这个问题，用两点之间的直线距离最为启发函数的A*算法是所有能得到最优解的算法中访问点最少的。启发函数对于特定的问题有特定的取法，那么A*作为一个搜索的算法框架用处还是挺多的。   

Dijkstra＋A* 求k短路径

当然这个算法不是我想出来的，这里只是说一下看后自己的理解。在A*算法中，优先队列出来的点如果扩展到了终点，那么 就得到了最短路径。如果能得到实际的评估函数(也就是h*(N))，那么第二次 从优先队列里面弹出来的就是第2段的路径，依次直到k短。如何得到h(N),就是图中各个点到T的实际最短路径距离，可以从图的反向图以T为源点进行 Dijkstra算法，最后Dist[N]就可以作为h(N)。然后以cnt[N]表示N点从优先队列里面弹出来的次数。K-shortest问题还有更快的解法，不过还没看，这里有大把论文。这里还分结果路径中是否可以有环，像现实中公路网肯定是要求无环的k-shortest path。下面这个算法是可以有环的。 

完整代码如下：   

//7040K 282MS
#include 

#include 
#include 
#include 
#include 
using namespace std;

const int MAXN=1001;
const int INF=(1<<20);
int N,M; //N个点 M条边

int S,T,K; //起点和终点
typedef struct _Edge
{
    int v;//边顶点

    int len;//边长度
}Edge;

int dist[MAXN];
int cnt[MAXN];

bool mark[MAXN];

struct Node{
    int v,len;
    Node() {};
    Node(int a,int b):v(a),len(b) {}
};

bool operator < (const Node& a,const Node& b)
{
    return (a.len+dist[a.v]>b.len+dist[b.v]);
}

vector Adj[MAXN];//图的邻接表表示
vector Rev[MAXN];//图的逆图

void Init_graph()
{
    int u,v,l;
    Edge edge;
    scanf("%d%d",&N;,&M;);
    for(int i=0;i"%d%d%d",&u;,&v;,&l;);
        edge.v=v;
        edge.len=l;
        Adj[u].push_back(edge);
        edge.v=u;
        Rev[v].push_back(edge);
    }
    scanf("%d%d%d",&S;,&T;,&K;);//计算S到T的第K短路径

    if(S==T) K++;
}

//Dijkstra 算法 找出各个点到T的最短距离
void Dijkstra()
{
    memset(mark,false,sizeof(mark));
    for(int i=1;i<=N;i++)
        dist[i]=INF;
    dist[T]=0;
    int u,v,min;
    while(1)
    {
        u=-1,min=INF;
        for(int i=1;i<=N;i++)
            if(!mark[i] && dist[i]if(u==-1) break;
        mark[u]=true;
        for(int k=0;kif(!mark[v] && dist[v]>dist[u]+Rev[u][k].len)
                dist[v]=dist[u]+Rev[u][k].len;
        }
    }
}

int Astar()
{
    if(dist[S]==INF) return -1;
    memset(cnt,0,sizeof(cnt));
    priority_queue<Node> Q;
    Q.push(Node(S,0));
    while(!Q.empty())
    {
        int len=Q.top().len;
        int v=Q.top().v;
        Q.pop();
        cnt[v]++;
        if(cnt[T]==K)
            return len;
        if(cnt[v]>K)
            continue;
        for(int i=0;ireturn -1;
}

int main()
{
    Init_graph();
    Dijkstra();
    int ans=Astar();
    printf("%d\n",ans);
    return 0;
}