POJ 2499 A*求第K短路

DES就是给你一个图。然后给你起点和终点。问你从起点到终点的第K短路。

第一次接触A*算法。

题目链接：Remmarguts' Date

转载：http://blog.csdn.net/mbxc816/article/details/7197228#plain

// 大概懂思路了。A*算法需要的估价函数里的两个函数、一个是起点到当前点的消耗。

//一个是当前点到目标点的估测消耗。所以需要用Dijstra或者Spfa求出目标点到所有点的最短路。

//然后就可以用A*算法来求了。

// 确实。学了位运算。链式表。

#include<cstdio>

#include<iostream>

#include<queue>

#include<string.h>

#define maxn 1005

#define maxm 200100

using namespace std;

struct Node{

  int v, c, n, nxt;

}Edge[maxm];

int head[maxn];

int tail[maxn];

int h[maxn];

struct Statement {

   int v, d, h;

   bool operator < (Statement a) const {

     return a.d+a.h<d+h;

   }

};

void addEdge (int u, int v, int c, int e)

{

    Edge[e<<].v = v;

    Edge[e<<].c = c;

    Edge[e<<].nxt = head[u];

    head[u] = e<<; // A*算法对周边的店扩展时按是从1到n;

    // 任意数|1相当于给这个数+1。

    Edge[e<<|].v = u;

    Edge[e<<|].c = c;

    Edge[e<<|].nxt = tail[v];

    tail[v] = e<<|; // Dijstra求最短路时、改为求t到其它所有节点的单源最短路

    return;

}

void Dijstra (int n, int s, int t)

{

    bool vis[maxn];

    memset(vis, , sizeof(vis));

    memset(h, 0x7F, sizeof(h));

    h[t] = ;

    for (int i=; i<=n; ++i) {

        int min = 0x7FFF;

        int k = -;

        for (int j=; j<=n; ++j) {

            if (vis[j] == false && min>h[j])

                min = h[j], k = j;

        }

        if (k == -) break;

        vis[k] = true;

        for (int temp=tail[k]; temp != -; temp=Edge[temp].nxt) {

            int v = Edge[temp].v;

            if (h[v] > h[k]+Edge[temp].c)

                h[v]=h[k]+Edge[temp].c;

        }

    }

}

int Astar_Kth (int n, int s, int t, int k)

{

    Statement cur, nxt;

    priority_queue<Statement>FstQ;

    int cnt[maxn];

    memset(cnt, , sizeof(cnt));

    cur.v = s; // 开启列表的第一个点、当前移动耗费和预估移动耗费。

    cur.d = ;

    cur.h = h[s];

    FstQ.push(cur);

    while(!FstQ.empty()) {

        cur = FstQ.top();

        FstQ.pop();

        cnt[cur.v]++;  // cnt[] 表示当前节点被扩展了几次。如果大于k 显然不符合题意。

        if (cnt[cur.v] > k) continue;  // 某个节点的第X次扩展。就说明这是该节点的第X短路、。

        if (cnt[t] == k) return cur.d; // 如果目标节点刚好被扩展了k次。说明找到第K短路。结束寻路、

        for (int temp=head[cur.v]; temp!=-; temp=Edge[temp].nxt) {

            int v = Edge[temp].v;

            nxt.d = cur.d + Edge[temp].c;

            nxt.v = v;

            nxt.h = h[v];

            FstQ.push(nxt);

        }

    }

    return -;

}

int main()

{

    int n, m;

    while(scanf("%d %d", &n, &m) != EOF) {

        int u, v, c;

        memset(head, -, sizeof(head));

        memset(tail, -, sizeof(tail));

        for (int i=; i<m; ++i) {

            scanf("%d %d %d", &u, &v, &c);

            addEdge(u, v, c, i);

        }

        int s, t, k;

        scanf("%d %d %d", &s, &t, &k);

        if (s == t) k++;

        Dijstra(n, s, t);

        printf("%d\n", Astar_Kth(n, s, t, k));

    }

    return ;

}

一天后。按照这个思路自己敲了一下。发现bug不止一点点。。而且有许多不懂的地方。主要因为不懂链表存储的原理、然后A*算法寻路的原理也很模糊。

#include<stdio.h>

#include<iostream>

#include<string.h>

#include<algorithm>

#include<queue>

using namespace std;

#define maxn 1005

#define maxm 200100

struct Node {  // 单源最短路径准备

   int v, c, nxt;

}Edge[maxm];

int head[maxn];

int tail[maxn];

int h[maxn]; // 保存目标节点到每个点的最短路径

struct Statement {  // 保存每个节点的估价函数的两个函数。和相连的下一个节点。

    int v, d, h;

    bool operator < (Statement a) const {  // 优先队列重载< 符号。

        return a.d+a.h < d+h;

    }

};

void addEdge (int u, int v, int c, int i)

{

    Edge[i<<].v = v;

    Edge[i<<].c = c;

    Edge[i<<].nxt = head[u];

    head[u] = i<<;

    Edge[i<<|].v = u;

    Edge[i<<|].c = c;

    Edge[i<<|].nxt = tail[v];

    tail[v] = i<<|;

    return;

}

void Dijstra (int n, int s, int t)

{

     bool vis[maxn];

     memset(vis, , sizeof(vis));

     memset(h, 0x7f, sizeof(h));

     // 刚开始写成了h[s] = 0.。。但是这是以t为源点求单源最短路径。所以。应该初始化为h[t] = 0;

     h[t] = ;

     for (int i=; i<=n; ++i) {

        int minn = 0x7f;

        int k = -;

        for (int j=; j<=n; ++j) {

            if (minn > h[j] && vis[j] == false) {

                k = j;

                minn = h[j];

            }

        }

        if (k == -) break;

        vis[k] = true;

        // 这里不是很理解。因为不懂链表的存储结构。

        for (int temp=tail[k]; temp!=-; temp=Edge[temp].nxt) {

            int v = Edge[temp].v;

            if (h[v] > Edge[temp].c + h[k])

                h[v] = Edge[temp].c + h[k];

        }

     }

}

int Astar_kth (int n, int s, int t, int k)

{

    Statement cur, nxt;

    priority_queue<Statement>FstQ;

    int cnt[maxn];

    memset(cnt, , sizeof(cnt));

    cur.v = s;

    cur.d = ;

    cur.h = h[s];

    FstQ.push(cur);

    while(!FstQ.empty()) {

     cur = FstQ.top();

     FstQ.pop();

     cnt[cur.v]++;

     //突然发现不太懂Ａ＊算法了。当前节点的扩展次数就是当前节点的第几短路。？？？

     if (cnt[cur.v] > k) continue;

     if (cnt[t] == k) return cur.d;

     //这里也不太懂。就是链表的问题。

     for (int temp=head[cur.v]; temp!=-; temp=Edge[temp].nxt) {

        int v = Edge[temp].v;

        nxt.d = cur.d+Edge[temp].c; // 走过的可以再走。没有限制。所以每次搜到的新节点的消耗 就是前一个节点已消耗的加上到当前节点的消耗。

        nxt.v = v;

        nxt.h = h[v];

        FstQ.push(nxt);

     }

    }

    return -;

}

int main()

{

    int n, m;

    while(~scanf("%d%d", &n, &m)) {

        memset(head, -, sizeof(head));

        memset(tail, -, sizeof(tail));

        for (int i=; i<m; ++i) {

            int a, b, t;

            scanf("%d%d%d", &a, &b, &t);

            addEdge(a, b, t, i);

        }

        int s, t, k;

        scanf("%d%d%d", &s, &t, &k);

        if (s == t) k++;  // s == t 时 貌似不能把0算作一条最短路。所以k++。

        Dijstra(n, s, t);

        int ans = Astar_kth(n, s, t, k);

        printf("%d\n", ans);

    }

    return ;

}