poj2249
A*算法
來自百度百科
A* 算法孕惜，A* （A-Star)算法是一種靜態(tài)路網(wǎng)中求解最短路徑最有效的直接搜索方法填大，也是解決許多搜索問題的有效算法脊凰。算法中的距離估算值與實際值越接近，最終搜索速度越快箭券。
公式表示為： ,
其中净捅， 是從初始狀態(tài)經(jīng)由狀態(tài)
到目標狀態(tài)的代價估計，
是在狀態(tài)空間中從初始狀態(tài)到狀態(tài)
的實際代價辩块，
是從狀態(tài)
到目標狀態(tài)的最佳路徑的估計代價蛔六。
（對于路徑搜索問題，狀態(tài)就是圖中的節(jié)點庆捺，代價就是距離）
的選取:
保證找到最短路徑（最優(yōu)解的）條件古今，關(guān)鍵在于估價函數(shù)的選取（或者說
的選忍弦浴）。
我們以表達狀態(tài)
到目標狀態(tài)的距離氓拼，那么
的選取大致有如下三種情況：
- 如果
到目標狀態(tài)的實際距離你画，這種情況下抵碟，搜索的點數(shù)多，搜索范圍大坏匪，效率低拟逮。但能得到最優(yōu)解。
- 如果
适滓，即距離估計
等于最短距離敦迄，那么搜索將嚴格沿著最短路徑進行， 此時的搜索效率是最高的凭迹。
- 如果
罚屋，搜索的點數(shù)少，搜索范圍小嗅绸，效率高脾猛，但不能保證得到最優(yōu)解。
所以取
模板
求一個圖中從源點 到終點
的第
短路
定義數(shù)組d[n],表示從 到
的距離鱼鸠，以
為源點做一次最短路可以得到每個點到
的距離猛拴，所以要存一個反向圖，用來預(yù)處理
d[n]蚀狰，直接以d[n]當作
有了d[n]之后愉昆，維護一個優(yōu)先隊列，隊列中的每個節(jié)點都存放{v,sum},v表示當前點麻蹋，sum表示到達點v一共走了多少距離跛溉。優(yōu)先隊列按照公式確定優(yōu)先級，其中
對應(yīng)
sum,對應(yīng)
d[v]哥蔚，通過優(yōu)先隊列一次次的擴展倒谷，如果第此取到
，那么此時的
sum就是到
的
短路糙箍。
其實就是s-v的距離加上v-t的距離渤愁，這就是一條路，我們可以知道每條路長度 深夯，所以可以找到第k短的那一條抖格，每次取到t，就是找到了一個比上次 次短 的路.
例題 POJ2249
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
#define MAXN 100009
int n,m,s,t,k;
int d[MAXN];// 每個點到t的距離
const int inf = 0x3f3f3f3f;
struct edge{
int to,len,next;
}e1[MAXN], e2[MAXN];
struct node{//優(yōu)先隊列中的節(jié)點
int v,sum;
node(int v,int w):v(v),sum(w){}
bool operator < (const node & o)const{
return this->sum+d[this->v] > o.sum+d[o.v]; // 這里就是估值小的放前面咕晋，f(v) = g(v) + h(v)雹拄，sum就是g(v),d[]做h(v)
}
};
int head1[MAXN], head2[MAXN] , js1,js2; //分別存 原圖，反向圖
bool vst[MAXN];
void init(){
js1 = 0;js2 = 0;
memset(head1,-1,sizeof(head1));
memset(head2,-1,sizeof(head2));
}
void add1(int a, int b, int len){//建原圖
e1[js1].to = b;
e1[js1].len = len;
e1[js1].next = head1[a];
head1[a] = js1;
js1++;
}
void add2(int a, int b, int len){//建反向圖
e2[js2].to = b;
e2[js2].len = len;
e2[js2].next = head2[a];
head2[a] = js2;
js2++;
}
void spfa(){//用反向圖初始化d[]
queue<int> que;
que.push(t);
memset(vst,0,sizeof(vst));
memset(d,inf,sizeof(d));
d[t]=0;
vst[t]=1;
while(!que.empty()){
int u=que.front(); que.pop();
vst[u]=0;
for(int i=head2[u]; i!=-1; i=e2[i].next){
int v=e2[i].to;
int w=e2[i].len;
if(d[u]+w < d[v]){
d[v] = d[u]+w;
//cout<<d[v]<<endl;
if(!vst[v]){
vst[v]=1;
que.push(v);
}
}
}
}
}
int astar(){//A* 算法
if(d[s]==inf) return -1;//說明沒有s到t的通路
priority_queue<node> que;
que.push(node(s,0)); //從s出發(fā)
int cnt=0; //記錄到達了多少次
while(!que.empty()){
node u = que.top(); que.pop();
if(u.v == t){
cnt++;
if(cnt == k)return u.sum;
}
for(int i=head1[u.v]; i!=-1; i=e1[i].next){
int v=e1[i].to;
int w=e1[i].len;
que.push( node(v, u.sum+w) );
}
}
return -1; //不存在k短路
}
int main(){
scanf("%d %d",&n, &m);
init();
for(int i=0;i<m;i++){
int a,b,len;
scanf("%d %d %d",&a,&b,&len);
add1(a,b,len);
add2(b,a,len); //反向圖
}
scanf("%d %d %d",&s,&t,&k);
if(s==t)k++; //poj2449這道題中掌呜，如果st重合滓玖，那么第一短結(jié)果肯定是0，原地不動不當作一條路看
spfa();//初始化估計值 d[]
int ac = astar();
printf("%d\n",ac);
return 0;
}
