第K短路

所谓K短路，就是从s到t的第K短的路，第1短就是最短路。

如何求第K短呢？有一种简单的方法是广度优先搜索，记录t出队列的次数，当t第k次出队列时，就是第k短路了。但点数过大时，入队列的节点过多，时间和空间复杂度都较高。

A*是在搜索中常用的优化，一种启发式搜索。简单的说，它可以用公式表示为f(n) = g(n) + f(n)，其中，f(n)是从s经由节点n到t的估价函数，g(n)是在状态空间中从s到n的实际代价，h(n)是从n到t的最佳路径估计代价。在设计中，要保证h(n)<= n到t的实际代价，这一点很重要，h(n)越接近真实值，速度越快。

由于启发函数的作用，使得计算机在进行状态转移时尽量避开不可能产生最优解的分支，而选择相对较接近最优解的路径进行搜索，降低了时间和空间复杂度。

算法过程：

1. 将图反向，用dijstra+heap求出t到所有点的最短距离，目的是求所有点到点t的最短路，用dis[i]表示i到t的最短路，其实这就是A*的启发函数，显然：h(n)<= n到t的实际代价。

2. 定义估价函数。我们定义g(n)为从s到n所花费的代价，h(n)为dis[n]，显然这符合A*算法的要求。

3. 初始化状态。状态中存放当前到达的点i,fi,gi。显然，fi=gi+dis[i]。初始状态为(S,dis[S],0)，存入优先级队列中。

4. 状态转移。假设当前状态所在的点v相邻的点u，我们可以得到转换：(V,fv,gv)-->(U,fu+w[v][u],gv+w[v][u])。

5. 终止条件。每个节点最多入队列K次，当t出队列K次时，即找到解。

例：POJ2449

题意：裸的K短路。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAX = 1005;
int n,m;
int start,end,k;
struct Edge
{
    int w;
    int to;
    int next;
};
Edge e[100005];
int head[MAX],edgeNum;
int dis[MAX];   //dis[i]表示从i点到end的最短距离
bool vis[MAX];
int cnt[MAX];
vector<Edge> opp_Graph[MAX];

struct Node
{
    int f,g;    //f = g+dis[v]
    int v;      //当前到达的节点
    Node(int a, int b,int c):f(a),g(b),v(c){}
    bool operator < (const Node& a) const
    {
        return a.f < f;
    }
};

void addEdge(int from, int to, int w)
{
    e[edgeNum].to = to;
    e[edgeNum].w = w;
    e[edgeNum].next = head[from];
    head[from] = edgeNum++;
}

void dijikastra(int start)
{
    int i;
    memset(vis,0,sizeof(vis));
    for(i = 1; i <= n; i++)
        dis[i] = INF;
    dis[start] = 0;
    priority_queue<Node> que;
    que.push(Node(0,0,start));
    Node next(0,0,0);
    while(!que.empty())
    {
        Node now = que.top();
        que.pop();
        if(vis[now.v])              //从集合T中选取具有最短距离的节点
            continue;
        vis[now.v] = true;          //标记节点已从集合T加入到集合S中
        for(i = 0; i < opp_Graph[now.v].size(); i++)    //更新从源点到其它节点(集合T中)的最短距离
        {
            Edge edge = opp_Graph[now.v][i];
            if(!vis[edge.to] && dis[now.v] + edge.w < dis[edge.to])     //加不加前面的判断无所谓
            {
                dis[edge.to] = dis[now.v] + edge.w;
                next.f = dis[edge.to];
                next.v = edge.to;
                que.push(next);
            }
        }
    }
}

int A_Star()
{
    int i;
    priority_queue<Node> que;
    if(dis[start] == INF)
        return -1;
    que.push(Node(dis[start],0,start));
    Node next(0,0,0);
    while(!que.empty())
    {
        Node now = que.top();
        que.pop();
        cnt[now.v]++;
        if(cnt[end] == k) return now.f;
        //严格最短路的判断条件为 cnt[end] == k&&now.f>min(zuiduanlu)
        if(cnt[now.v] > k)
            continue;
        for(i = head[now.v]; i != -1; i = e[i].next)
        {
            next.v = e[i].to;
            next.g = now.g + e[i].w;
            next.f = next.g + dis[e[i].to];
            que.push(next);
        }
    }
    return -1;
}

int main()
{
    int i;
    int from,to,w;
    edgeNum = 0;
    memset(head,-1,sizeof(head));
    memset(opp_Graph,0,sizeof(opp_Graph));
    memset(cnt,0,sizeof(cnt));
    scanf("%d %d",&n,&m);
    Edge edge;
    for(i = 1; i <= m; i++)
    {
        scanf("%d %d %d",&from,&to,&w);
        addEdge(from,to,w);
        edge.to = from;
        edge.w = w;
        opp_Graph[to].push_back(edge);
    }
    scanf("%d %d %d",&start,&end,&k);
    if(start == end)
        k++;
    dijikastra(end);
    int result = A_Star();
    printf("%d\n",result);
    return 0;
}

相关文章