所谓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;
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;
}
分享到:
相关推荐
astar 启发式搜索求第k短路。主要运用的贪心加优先队列的思想。
这是运用C++求出来的第k短路,属于图论
A-star和第k短路和次小生成树和Yen和MPS寻路算法.doc
实现K最短路算法,包括双向图算法(删除法)、单向无环图算法(附加节点法)。VC7、VC6都可通过编译。算法原理可在CSDN上找到一堆论文。
A* dijstra k短路 求法:反向建边 通过dijstra做预处理 最短路作为A*的评估函数 通过A* 将目标点出队列K次 如果原点和终点相同出栈K+1次
物流路径优化K短路matlab程序,可以运行,在此平台分享大家一起学习
k短路算法,有算法的说明和程序的源码
k则最短路算法文献,理论严密算法中的删除路径算法,santos。
Yen算法求前K短路,无向图中求Yen算法求前K短无环路。
使用C++ 编写的K短路计算方法,基于先进的双扫描法(doublesweep),效率较高
对于K最短路问题,首先找出两点之间的所有路径,然后利用K最短路算法,将最短路、次短路、第三最短路等计算出来,存入数组中。该matlab程序具有很好的通用性,希望对大家有用。 说明:findpath.m文件可计算出任意两...
本资源是http://write.blog.csdn.net/postedit/50428251 进阶01——考虑换乘的基于路径长度的所有点间K短路算法的计算结果。
acm算法书,acmer必用的算法书。 目录 语言相关 常见基础错误 基础知识 枚举 模拟 ...次短路与第K短路 最近公共祖先 LCA 最小生成树 Kruskal 最小树形图 一般图的最大匹配 最大流 Dinic 最小割 费用流
在最短路算法基础上编制的k短路算法,简洁方便,很容易套用
是一个求解k条最短路的matlab代码,和大家分享,也希望大家多多讨论批评
很棒的程序 解决 k shortest path 的 c 与java
轨道交通配流应用-基于蚁群算法求解K短路问题python源码(带项目说明和代码注释).zip 【资源介绍】 K短路求解算法: # 对于K短路的求解,本设计采用了比较简单的策略,即在蚂蚁搜索食物的过程中,对于返回的路径进行...
图论- k 短路.rar
单亲遗传算法求解k短路问题(KSP)--原创算法