Dijkstra搜索算法

时间:2022-09-02 17:11:18
Dijkstra无向图

Dijkstra搜索算法

算法执行步骤如下:

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搜索算法的更多相关文章

  1. 【小白学游戏常用算法】二、A&ast;启发式搜索算法

    在上一篇博客中,我们一起学习了随机迷宫算法,在本篇博客中,我们将一起了解一下寻路算法中常用的A*算法. 通常情况下,迷宫寻路算法可以使用深度优先或者广度优先算法,但是由于效率的原因,不会直接使用这些算 ...

  2. 网格最短路径算法(Dijkstra &amp&semi; Fast Marching)

    Dijkstra算法是计算图中节点之间最短路径的经典算法,网上关于Dijkstra算法原理介绍比较多,这里不再多讲.值得一提的是,当图中节点之间的权重都为1时,Dijkstra算法就变化为一般意义上的 ...

  3. 最短路径之迪杰斯特拉(Dijkstra)算法

    迪杰斯特拉(Dijkstra)算法主要是针对没有负值的有向图,求解其中的单一起点到其他顶点的最短路径算法.本文主要总结迪杰斯特拉(Dijkstra)算法的原理和算法流程,最后通过程序实现在一个带权值的 ...

  4. 网格最短路径算法(Dijkstra &amp&semi; Fast Marching)&lpar;转&rpar;

    Dijkstra算法是计算图中节点之间最短路径的经典算法,网上关于Dijkstra算法原理介绍比较多,这里不再多讲.值得一提的是,当图中节点之间的权重都为1时,Dijkstra算法就变化为一般意义上的 ...

  5. 图论基础之Dijkstra算法的初探

         图论,顾名思义就是有图有论.        图:由点"Vertex"和边"Edge "组成,且图分为有向图和无向图(本文讨论有向图),之前做毕业设计的 ...

  6. 聪明的搜索算法’ A&ast;算法

    A*算法     是一种启发式的搜索算法. 了解BFS.DFS或者Dijkstra算法的人应该知道.这些算法都是一种向四周盲目式搜索的方法.   启发式搜索:     启发式搜索就是在状态空间中的搜索 ...

  7. A&ast;搜索算法

    先了解一下什么是A*算法. A*搜寻算法,俗称A星算法.A*算法是用于寻找两点之间的最短路径,同时它也是一种静态路网中求解最短路最有效的直搜索方法.这是一种在图形平面上,有多个节点的路径,求出最低通过 ...

  8. 图的最短路径-----------Dijkstra算法详解(TjuOj2870&lowbar;The Kth City)

    做OJ需要用到搜索最短路径的题,于是整理了一下关于图的搜索算法: 图的搜索大致有三种比较常用的算法: 迪杰斯特拉算法(Dijkstra算法) 弗洛伊德算法(Floyd算法) SPFA算法 Dijkst ...

  9. AI贪吃蛇前瞻——基于Dijkstra算法的最短路径问题

    在贪吃蛇流程结构优化之后,我又不满足于亲自操刀控制这条蠢蠢的蛇,干脆就让它升级成AI,我来看程序自己玩,哈哈. 一.Dijkstra算法原理 作为一种广为人知的单源最短路径算法,Dijkstra用于求 ...

随机推荐

  1. IOS手动添加CoreData

    手动添加coreData: 1.在target-build phrase-Link binary with libraries里增加CoreData Framework 2.加入数据模型:comman ...

  2. 算法与数据结构实验题 5&period;2 Missile

    1.题目: 2.解题思路: 把每个点对应的两条半径求出,之后对d1进行升序排序,对应d2也改变位置.其中一个圆心的半径r1确定之后,除去第一个圆包围的点,在其余点中找到另外一个圆的最长的半径r2,此时 ...

  3. Java——jdk1&period;5新特性

     /* * 可变参数:--一个方法的参数个数不固定. * 特点: *  只能出现在参数列表的最后. *  调用可变参数的方法时,编译器为该可变参数隐含创建一个数组,在方法体中以数组的形式访问可变参 ...

  4. 最简单的视音频播放演示样例8:DirectSound播放PCM

    ===================================================== 最简单的视音频播放演示样例系列文章列表: 最简单的视音频播放演示样例1:总述 最简单的视音频 ...

  5. HDU 3506 Monkey Party(区间DP)题解

    题意:有n个石堆排成环,每次能合并相邻的两堆石头变成新石堆,代价为新石堆石子数,问最少的总代价是多少 思路:先看没排成环之前怎么做:用dp[i][j]表示合并i到j所需的最小代价,那么dp[i][j] ...

  6. 关于IT个人看法

    对于理科生来说,理论和技术都是相当重要的,我很爱钻牛角尖,但是请理解‘固执的我’, 本人选择IT行业,其实也是偶然,带着质疑的眼光,成为了众多IT男中毫无‘特色’的一员,回忆 学习阶段,逐渐认识了IT ...

  7. FastAdmin 的前端环境怎么安装?

    FastAdmin 的前端环境怎么安装? 安装 Git 安装 Node.js 安装 cnpm 安装 bower 开始安装 FastAdmin 的前端组件 bower install bower upd ...

  8. &lbrack;转&rsqb;eclipse 配置黑色主题 Luna 方式三

      虽然以前也使用eclipse的黑色主题,但是配置起来稍微麻烦一点. 这里先声明,下面的方式适合最新版本的Eclipse Luna,旧的版本可以下载我提供的这个插件,并将其放在eclipse目录下的 ...

  9. oracle ocp题库变化,052最新考试题及答案整理-30

    30.Which is true when a database instance is shut down? A. Only transactional and normal modes wait ...

  10. redis&lpar;2&rpar;数据类型

    一.数据类型 redis的数据结构是key-value的键值对的形式,但是它和传统String-String的键值对形式不一样,它的value不仅仅是string类型,而是有着丰富的数据类型,如: 1 ...