最短路径算法的研究毕业设计

最短路径算法的研究毕业设计内容摘要：

10 999999 50 999999 999999 999999 50 999999 20 10 30 999999 20 999999 60 8 100 999999 10 60 999999 A* 算法 算法介绍及适用条件和范围 A*（ AStar）算法是一种静态路网中求解最短路径最有效的方法； 公式表示为 ： f(n)=g(n)+h(n), 其中 f(n) 是从初始点经由节点 n 到目标点的估价函数， g(n) 是在状态空间中从初始节点到 n 节点的实际代价， h(n)是从 n 到目标节点最佳路径的估计代价 A*算法属于一种启发式搜索。 它扩展结点的次序类似于广度优先搜索，但不同的是每生成一个子结点需要计算估价函数 F，以估算起始结点到该结点的代价及它到达目标结点的代价的和；每当扩展结点时，总是在所有待扩展结点中选择具有最小 F值的结点作为扩展对象，以便使搜索尽量沿最有希望的方向进行。 因此， A*算法只 要求产生问题的全部状态空间的部分结点，就可以求解问题了，搜索效率较高。 确定估价函数方法通常是：搜索到该结点的深度 + 距离目标最近的程度。 如图有如下的状态空间：（起始位置是 A，目标位置是 P，字母后的数字表示节点的估价值） 状态空间图 搜索过程中设置两个表： OPEN 和 CLOSED。 OPEN 表保存了所有已生成而未考察的节点， CLOSED 表中记录已访问过的节点。 算法中有一步是根据估价函数重排 OPEN 表。 这样循环中的每一步只考虑 OPEN 表中状态最好的节点。 9 算法描述和算法实现 算法描述及其实现 （ 1） 初始状态： OPEN=[A5]。 CLOSED=[]。 （ 2） 估算 A5，取得搜有子节点，并放入 OPEN 表中； OPEN=[B4, C4, D6]。 CLOSED=[A5] （ 3） 估算 B4，取得搜有子节点，并放入 OPEN 表中； OPEN=[C4, E5, F5, D6]。 CLOSED=[B4, A5] （ 4） 估算 C4；取得搜有子节点，并放入 OPEN 表中； OPEN=[H3, G4, E5, F5, D6]。 CLOSED=[C4, B4, A5] （ 5） 估算 H3，取得搜有子节点，并放入 OPEN 表中； OPEN=[O2, P3, G4, E5, F5, D6]。 CLOSED=H3C4, B4, A5] （ 6） 估算 O2，取得搜有子节点，并放入 OPEN 表中； OPEN=[P3, G4, E5, F5, D6]。 CLOSED=[O2, H3, C4, B4, A5] （ 7） 估算 P3，已得到解。 具体算法分析 在国际象棋的棋盘上，一匹马共有 8 个可能的跳跃方向，求从起点到目标点之间的最少跳跃次数。 include iostream include queue using namespace std。 struct knight{ int x,y,step。 int g,h,f。 bool operator (const knight amp。 k) const{ //重载比较运算符 return f。 } }k。 bool visited[8][8]。 //已访问标记 (关闭列表 ) int x1,y1,x2,y2,ans。 //起点 (x1,y1),终点 (x2,y2),最少移动次数 ans int dirs[8][2]={{2,1},{2,1},{2,1},{2,1},{1,2},{1,2},{1,2}, 10 {1,2}}。 //8个移动方向 priority_queueknight que。 //最小优先级队列 (开启列表 ) bool in(const knight amp。 a){ //判断 knight 是否在棋盘内 if(0 || 0 || =8 || =8) return false。 return true。 } int Heuristic(const knight amp。 a){ //manhattan 估价函数 return (abs()+abs())*10。 } void Astar(){ //A*算法 knight t,s。 while(!()){ t=(),(),visited[][]=true。 if(==x2 amp。 amp。 ==y2){ ans=。 break。 } for(int i=0。 i8。 i++){ =+dirs[i][0],=+dirs[i][1]。 if(in(s) amp。 amp。 !visited[][]){ = + 23。 //23 表示根号 5 乘以 10 再取其 ceil = Heuristic(s)。 = +。 = + 1。 (s)。 } } } } int main(){ char line[5]。 11 while(gets(line)){ x1=line[0]39。 a39。 ,y1=line[1]39。 139。 ,x2=line[3]39。 a39。 ,y2=line[4]39。 139。 memset(visited,false,sizeof(visited))。 =x1,=y1,==0,=Heuristic(k),=+。 while(!()) ()。 (k)。 Astar()。 printf(To get from %c%c to %c%c takes %d knight moves.\n,line[0],line[1],line[3],line[4],ans)。 } return 0。 } BellmanFord 算法 算法介绍及适用条件和范围 BellmanFord 算法能在更普遍的情况下（存在负权边）解决单源点最短路径问题。 对于给定的带权（有向或无向）图 G=（ V,E），其源点为 s，加权函数 w 是 边集 E 的映射。 对图 G 运行 BellmanFord算法的结果是一个布尔值，表明图中是否存在着一个从源点 s 可达的负权回路。 若不存在这样的回路，算法将给出从源点 s 到 图 G 的任意顶点 v 的最短路径 d[v]。 （ 1） 单源最短路径 (从源点 s 到其它 所有顶点 v)； （ 2） 有向图和无向图 (无向图可以看作 (u,v),(v,u)同属于边集 E 的有向图 )； （ 3） 边权可正可负 (如有负权回路输出错误提示 )； （ 4） 差分约束系统 算法描述和算法实现 12 1,.初始化：将除源点外的所有顶点的最短距离估计值 d[v] ←+∞, d[s] ←0。 ：反复对边集 E中的每条边进行松弛操作，使得顶点集 V中的每个顶点 v 的最短距离估计值逐步逼近其最短距离；（运行 |v|1 次） ：判断边集 E中的每一条边的两个端点是否收敛。 如果存在未收敛的顶点，则算法返回 false，表明问题无解；否则算法返回 true，并且从源点可达的顶点 v 的最短距离保存在 d[v]中。 （ 1） PASCA 语言 For i:=1 to |V|1 do For 每条边 (u,v)∈ E do Relax(u,v,w)。 For 每条边 (u,v)∈ E do If dis[u]+wdis[v] Then Exit(False) （ 2） C/C++语言 void bellman_ford(int v) { for 1 to n initialize dist[v]。 for 2 to n1 (i) for 1 to n (j) for 1 to n (k) if edge[k][j] 0 amp。 amp。 dist[k] edge[k][j]+dist[j] 更新当前值 } 具体算法设计 typedef struct oo { int len,num。 struct oo *next。 } link。 typedef struct { int num。 13 link *next。 } graph。 /* node[]图的邻接表 n 节点总数 s 源点 dis[]到源点的最短路径长度 pre[]最短路径上的前驱结点 算法返回 true，当且仅当途中不包含从源点可达的负权回路 */ bool bellmanFord(graph node[],int n,int s) { int dis[MAX],pre[MAX]。 int i,j。 link *p。 for(i=0。 in。 i++) { dis[i]=MAXVALUE。 pre[i]=1。 } dis[s]=0。 for(i=0。 in。 i++) { p=node[i].next。 while(p) { if(plen+dis[i]dis[pnum]) {dis[pnum]=plen+dis[i]。 pre[pnum]=i。 } p=pnext。 } p=node[i].next。 while(p) { if(plen+dis[i]dis[pnum]) 14 return false。 p=pnext。 } } for(i=0。 in。 i++) { printf(%d %d\n,i,dis[i])。 j=i。 while(j!=1) { printf(%d ,j)。 j=pre[j]。 } coutendl。 } return true。 } //这个是邻接矩阵 const int MAX = 100。 const int MAXVALUE = 1000。 int graph[MAX][MAX],n。 /* graph[][]图的邻接阵 n 图的节点数 s 源点 dis[] 存放最短路径 pre[] 存放最短路径上的前驱节点。