Dijkstra无向图算法执行步骤如下:
上面两张图来源于:http://blog.csdn.net/v_july_v/article/details/6096981
很牛的大神,膜拜,此处有鲜花
Dijkstra 的算法实现
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map; public class Dijkstra {
List<verPoint>Graph; public List<verPoint> getGraph() {
return Graph;
} public void setGraph(List<verPoint> graph) {
Graph = graph;
} public double minDistance(double minD,Map<Integer,Double>distance,List<verPoint>Graph,List<verPoint>S,List<verPoint>U){ if(S==null){
S = new ArrayList();
U = new ArrayList();
S.add(Graph.get(0));
for(int i = 0;i<Graph.size();i++){
if(!S.contains(Graph.get(i))){
U.add(Graph.get(i));
}
}
}
if(S.size()==Graph.size()){ return minD;
}
verPoint nowPoint = S.get(S.size()-1); Map <Integer,Double>newdistance = new HashMap();
double []dis = new double[U.size()];
for(int i = 0;i<U.size();i++){
dis[i] = minD + nowPoint.distancePoint(U.get(i));//直接加上到U.get(i)的距离
if(dis[i]>distance.get(U.get(i).getId())){//与上一次到U.get(i)距离的比较
dis[i]=distance.get(U.get(i).getId());
}
newdistance.put(U.get(i).getId(), dis[i]);
} //寻找dis中最小的值所对应的索引值
int mindex = 0;
for(int i = 1;i<dis.length;i++){
if(dis[mindex]>dis[i]){
mindex = i;
}
}
double newMinD = dis[mindex];
S.add(U.get(mindex));
U.remove(mindex);
for(int i = 0;i<S.size();i++){
System.out.print(" "+S.get(i).getVerName());
}
System.out.println();
double min = minDistance(newMinD,newdistance,Graph,S,U);
return min;
} }应当注意的是:
1、minD存储的是每次搜寻后当前点与初始点之间的最小距离
2、distance中存储的是仍在open中的点到初始点的最小距离
3、每次循环的时候,首先将未在S中的点放入U中。S表示路径,U表示剩余点;
其次,计算S最后面的一点到U中每个点的距离,并且如果上一次也到过U中某个节点,则注意比较这两次到同一节点的距离,取更小的。然后取U中各节点最小距离,并放入S中直至S中元素等于图的元素个数
Dijkstra搜索算法的更多相关文章
-
【小白学游戏常用算法】二、A*启发式搜索算法
在上一篇博客中,我们一起学习了随机迷宫算法,在本篇博客中,我们将一起了解一下寻路算法中常用的A*算法. 通常情况下,迷宫寻路算法可以使用深度优先或者广度优先算法,但是由于效率的原因,不会直接使用这些算 ...
-
网格最短路径算法(Dijkstra &; Fast Marching)
Dijkstra算法是计算图中节点之间最短路径的经典算法,网上关于Dijkstra算法原理介绍比较多,这里不再多讲.值得一提的是,当图中节点之间的权重都为1时,Dijkstra算法就变化为一般意义上的 ...
-
最短路径之迪杰斯特拉(Dijkstra)算法
迪杰斯特拉(Dijkstra)算法主要是针对没有负值的有向图,求解其中的单一起点到其他顶点的最短路径算法.本文主要总结迪杰斯特拉(Dijkstra)算法的原理和算法流程,最后通过程序实现在一个带权值的 ...
-
网格最短路径算法(Dijkstra &; Fast Marching)(转)
Dijkstra算法是计算图中节点之间最短路径的经典算法,网上关于Dijkstra算法原理介绍比较多,这里不再多讲.值得一提的是,当图中节点之间的权重都为1时,Dijkstra算法就变化为一般意义上的 ...
-
图论基础之Dijkstra算法的初探
图论,顾名思义就是有图有论. 图:由点"Vertex"和边"Edge "组成,且图分为有向图和无向图(本文讨论有向图),之前做毕业设计的 ...
-
聪明的搜索算法’ A*算法
A*算法 是一种启发式的搜索算法. 了解BFS.DFS或者Dijkstra算法的人应该知道.这些算法都是一种向四周盲目式搜索的方法. 启发式搜索: 启发式搜索就是在状态空间中的搜索 ...
-
A*搜索算法
先了解一下什么是A*算法. A*搜寻算法,俗称A星算法.A*算法是用于寻找两点之间的最短路径,同时它也是一种静态路网中求解最短路最有效的直搜索方法.这是一种在图形平面上,有多个节点的路径,求出最低通过 ...
-
图的最短路径-----------Dijkstra算法详解(TjuOj2870_The Kth City)
做OJ需要用到搜索最短路径的题,于是整理了一下关于图的搜索算法: 图的搜索大致有三种比较常用的算法: 迪杰斯特拉算法(Dijkstra算法) 弗洛伊德算法(Floyd算法) SPFA算法 Dijkst ...
-
AI贪吃蛇前瞻——基于Dijkstra算法的最短路径问题
在贪吃蛇流程结构优化之后,我又不满足于亲自操刀控制这条蠢蠢的蛇,干脆就让它升级成AI,我来看程序自己玩,哈哈. 一.Dijkstra算法原理 作为一种广为人知的单源最短路径算法,Dijkstra用于求 ...
随机推荐
-
IOS手动添加CoreData
手动添加coreData: 1.在target-build phrase-Link binary with libraries里增加CoreData Framework 2.加入数据模型:comman ...
-
算法与数据结构实验题 5.2 Missile
1.题目: 2.解题思路: 把每个点对应的两条半径求出,之后对d1进行升序排序,对应d2也改变位置.其中一个圆心的半径r1确定之后,除去第一个圆包围的点,在其余点中找到另外一个圆的最长的半径r2,此时 ...
-
Java——jdk1.5新特性
/* * 可变参数:--一个方法的参数个数不固定. * 特点: * 只能出现在参数列表的最后. * 调用可变参数的方法时,编译器为该可变参数隐含创建一个数组,在方法体中以数组的形式访问可变参 ...
-
最简单的视音频播放演示样例8:DirectSound播放PCM
===================================================== 最简单的视音频播放演示样例系列文章列表: 最简单的视音频播放演示样例1:总述 最简单的视音频 ...
-
HDU 3506 Monkey Party(区间DP)题解
题意:有n个石堆排成环,每次能合并相邻的两堆石头变成新石堆,代价为新石堆石子数,问最少的总代价是多少 思路:先看没排成环之前怎么做:用dp[i][j]表示合并i到j所需的最小代价,那么dp[i][j] ...
-
关于IT个人看法
对于理科生来说,理论和技术都是相当重要的,我很爱钻牛角尖,但是请理解‘固执的我’, 本人选择IT行业,其实也是偶然,带着质疑的眼光,成为了众多IT男中毫无‘特色’的一员,回忆 学习阶段,逐渐认识了IT ...
-
FastAdmin 的前端环境怎么安装?
FastAdmin 的前端环境怎么安装? 安装 Git 安装 Node.js 安装 cnpm 安装 bower 开始安装 FastAdmin 的前端组件 bower install bower upd ...
-
[转]eclipse 配置黑色主题 Luna 方式三
虽然以前也使用eclipse的黑色主题,但是配置起来稍微麻烦一点. 这里先声明,下面的方式适合最新版本的Eclipse Luna,旧的版本可以下载我提供的这个插件,并将其放在eclipse目录下的 ...
-
oracle ocp题库变化,052最新考试题及答案整理-30
30.Which is true when a database instance is shut down? A. Only transactional and normal modes wait ...
-
redis(2)数据类型
一.数据类型 redis的数据结构是key-value的键值对的形式,但是它和传统String-String的键值对形式不一样,它的value不仅仅是string类型,而是有着丰富的数据类型,如: 1 ...