misschuer

常用链接

统计

积分与排名

百事通

最新评论

A*算法求第k短路

参考了http://blog.myspace.cn/e/404763245.htm
  1 /*
  2 **下面给出自己写的邻接表形式采用SPFA计算启发函数的效率表示一般的K短路代码
  3 **表示可以当成模板,这个不是最好的代码, 不过一般情况下都可以的吧,现在去尝试下用A*做迷宫问题.据说效率不是一般的高
  4 **/
  5 #include <iostream>  6 #include <queue>
  7 #include <cstring>
  8 #include <cstdio>
  9 using namespace std;
 10 #define MAXV 1001
 11 #define MAXE 100000
 12 #define INF 100000000
 13 
 14 typedef struct {
 15 
 16   int v;
 17   int val;
 18   int next;
 19 }Edge;
 20 
 21 Edge e[MAXE];
 22 int p[MAXV], eid, n;
 23 
 24 void add(int u, int v, int val) {
 25 
 26   e[eid].next = p[ u ];
 27   e[eid].v    =      v;
 28   e[eid].val  =    val;
 29   p[u]        = eid ++;
 30 }
 31 
 32 //建立反向图 为了计算启发函数h(x)(即结点x到T的最短距离)
 33 Edge op[MAXE];
 34 int oph[MAXV], opid;
 35 
 36 void addop(int u, int v, int val) {
 37 
 38   op[opid].next = oph[ u ];
 39   op[opid].v    =        v;
 40   op[opid].val  =      val;
 41   oph[ u ]      =  opid ++;
 42 }
 43 
 44 
 45 int dis[MAXV], S, T, K;
 46 
 47 struct Node {
 48 
 49   int v;
 50   int val;
 51   friend bool operator <(Node a, Node b) {
 52 
 53     return a.val + dis[a.v] > b.val + dis[b.v];
 54   }
 55 };
 56 
 57 void init() {
 58 
 59     for(int i = 0; i <= n; ++ i) {
 60 
 61       p[ i ] = -1;
 62       dis[ i ] = INF;
 63       oph[ i ] = -1;
 64     }
 65     eid = 0;
 66     opid = 0;
 67 }
 68 
 69 void spfa() {
 70 
 71     dis[ T ] = 0;
 72     queue<int> Q;
 73     Q.push(T);
 74     while(!Q.empty()) {
 75 
 76       int u = Q.front();
 77           Q.pop();
 78           
 79       for(int j = oph[ u ]; j != -1; j = op[ j ].next) {
 80 
 81         int v = op[ j ].v;
 82         int val = op[ j ].val;
 83         if(dis[ v ] > dis[ u ] + val) {
 84 
 85            dis[ v ] = dis[ u ] + val;
 86            Q.push(v);
 87         }
 88       }
 89     }
 90 }
 91 
 92 void  A_star() {
 93 
 94   spfa();
 95   int vist[MAXV];
 96   if(dis[S] == INF) {
 97 
 98     puts("-1");
 99     return ;
100   }
101   memset(vist, 0sizeof(vist));
102   priority_queue<Node> Q;
103   Node t;
104   t.v = S;
105   t.val = 0;
106   Q.push(t);
107   int u;
108   int val;
109   while(!Q.empty()) {
110 
111     t = Q.top();
112     Q.pop();
113     u = t.v;
114     val = t.val;
115     
116     vist[ u ] ++;
117     
118     if(vist[ u ] > K) continue;
119     if(u == T && vist[ u ] == K) break;
120 
121     for(int j = p[ u ]; j != -1; j = e[ j ].next) {
122 
123         t.v = e[ j ].v;
124         t.val = val + e[ j ].val;
125         Q.push(t);
126     }
127   }
128   if(u == T && vist[ u ] == K) {
129 
130     printf("%d\n", val);
131     return ;
132   }
133   
134   puts("-1");
135 }
136 
137 int main() {
138 
139   int m;
140   while(~scanf("%d %d"&n, &m)) {
141 
142        init();
143        while(m --) {
144 
145          int u, v, val;
146          scanf("%d %d %d"&u, &v, &val);
147          add(u, v, val);
148          addop(v, u, val);
149        }
150        scanf("%d %d %d"&S, &T, &K);
151        if(S == T) K ++;
152        A_star();
153   }
154   return 0;
155 }

/*表示上面写的不是SPFA, 貌似是BFS+DP,现在改正一下,效率提高了一点*/
void spfa() {

    
bool vist[MAXV];
    memset(vist, 
falsesizeof(vist));
    dis[ T ] 
= 0;
    queue
<int> Q;
    Q.push(T);
    
while(!Q.empty()) {

      
int u = Q.front();
          Q.pop();
      vist[ u ] 
= false;
      
for(int j = oph[ u ]; j != -1; j = op[ j ].next) {

        
int v = op[ j ].v;
        
int val = op[ j ].val;
        
if(dis[ v ] > dis[ u ] + val) {

           dis[ v ] 
= dis[ u ] + val;
           
if(!vist[ v ]) {
           
               vist[ v ] 
= true;
               Q.push(v);
           }

        }

      }

    }

}


struct Point {

    
int v;
    
int val;
    friend 
bool operator <(Point a, Point b) {
    
        
return a.val > b.val;
    }

}
;


void dijkstra() {

    
bool vist[MAXV];
    
int u;
    memset(vist, 
falsesizeof(vist));
    priority_queue
<Point> Q;
    Point t;
    t.v 
= T; t.val = 0;  Q.push(t);
    
while(!Q.empty()) {

      t 
= Q.top(); Q.pop();
      u 
= t.v;
      
if(vist[ u ]) continue;
      vist[ u ] 
= true;
      dis[ u ] 
= t.val;

      
for(int j = oph[ u ]; j != -1; j = op[ j ].next) {

        
int v = op[ j ].v;
        
if(!vist[ v ]) {

            
int val = op[ j ].val;
            Point tmp;
            tmp.v 
= v;
            tmp.val 
= t.val + val;
            Q.push(tmp);
        }

      }

    }

}

三者的效率SPFA最高,dijkstra次之,BFS+dp最慢;如果代码有可以优化的地方请留言,谢谢

posted on 2011-04-25 19:22 此最相思 阅读(664) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理