迪杰斯特拉算法java

1. 图遍历算法之最短路径Dijkstra算法

最短路径问题是图论研究中一个经典算法问题，旨在寻找图中两节点或单个节点到其他节点之间的最短路径。根据问题的不同，算法的具体形式包括：

常用的最短路径算法包括：Dijkstra算法，A 算法，Bellman-Ford算法，SPFA算法（Bellman-Ford算法的改进版本），Floyd-Warshall算法，Johnson算法以及Bi-direction BFS算法。本文将重点介绍Dijkstra算法的原理以及实现。

Dijkstra算法，翻译作戴克斯特拉算法或迪杰斯特拉算法，于1956年由荷兰计算机科学家艾兹赫尔.戴克斯特拉提出，用于解决赋权有向图的 单源最短路径问题 。所谓单源最短路径问题是指确定起点，寻找该节点到图中任意节点的最短路径，算法可用于寻找两个城市中的最短路径或是解决着名的旅行商问题。

问题描述 ：在无向图 中， 为图节点的集合， 为节点之间连线边的集合。假设每条边 的权重为 ，找到由顶点 到其余各个节点的最短路径（单源最短路径）。

为带权无向图，图中顶点 分为两组，第一组为已求出最短路径的顶点集合（用 表示）。初始时 只有源点，当求得一条最短路径时，便将新增顶点添加进 ，直到所有顶点加入 中，算法结束。第二组为未确定最短路径顶点集合（用 表示），随着 中顶点增加， 中顶点逐渐减少。

以下图为例，对Dijkstra算法的工作流程进行演示（以顶点 为起点）：

注：
01） 是已计算出最短路径的顶点集合；
02） 是未计算出最短路径的顶点集合；
03） 表示顶点 到顶点 的最短距离为3
第1步 ：选取顶点 添加进

第2步 ：选取顶点 添加进 ，更新 中顶点最短距离

第3步 ：选取顶点 添加进 ，更新 中顶点最短距离

第4步 ：选取顶点 添加进 ，更新 中顶点最短距离

第5步 ：选取顶点 添加进 ，更新 中顶点最短距离

第6步 ：选取顶点 添加进 ，更新 中顶点最短距离

第7步 ：选取顶点 添加进 ，更新 中顶点最短距离

示例：node编号1-7分别代表A,B,C,D,E,F,G

(s.paths <- shortest.paths(g, algorithm = "dijkstra"))输出结果：

(s.paths <- shortest.paths(g,4, algorithm = "dijkstra"))输出结果：

示例：

找到D（4）到G（7）的最短路径：

[1] 维基网络，最短路径问题： https://zh.wikipedia.org/wiki/%E6%9C%80%E7%9F%AD%E8%B7%AF%E9%97%AE%E9%A2%98 ；
[2]CSDN，Dijkstra算法原理： https://blog.csdn.net/yalishadaa/article/details/55827681 ;
[3]RDocumentation: https://www.rdocumentation.org/packages/RNeo4j/versions/1.6.4/topics/dijkstra ;
[4]RDocumentation: https://www.rdocumentation.org/packages/igraph/versions/0.1.1/topics/shortest.paths ;
[5]Pypi: https://pypi.org/project/Dijkstar/

2. dijkstra算法是什么

迪杰斯特拉算法用来解决从顶点v0出发到其余顶点的最短路径，该算法按照最短路径长度递增的顺序产生所以最短路径。

对于图G=（V，E），将图中的顶点分成两组：第一组S：已求出的最短路径的终点集合（开始为｛v0}）。第二组V-S：尚未求出最短路径的终点集合（开始为V-{v0}的全部结点）。

堆优化

思考

该算法复杂度为n^2,我们可以发现，如果边数远小于n^2,对此可以考虑用堆这种数据结构进行优化，取出最短路径的复杂度降为O(1)；每次调整的复杂度降为O（elogn）；e为该点的边数，所以复杂度降为O((m+n)logn)。

实现

1、将源点加入堆，并调整堆。

2、选出堆顶元素u（即代价最小的元素），从堆中删除，并对堆进行调整。

3、处理与u相邻的，未被访问过的，满足三角不等式的顶点

1):若该点在堆里，更新距离，并调整该元素在堆中的位置。

2):若该点不在堆里，加入堆，更新堆。

4、若取到的u为终点，结束算法；否则重复步骤2、3。

3. java 最短路径算法 如何实现有向 任意两点

Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式

用OPEN,CLOSE表的方式，其采用的是贪心法的算法策略，大概过程如下：

1、声明两个集合，open和close，open用于存储未遍历的节点，close用来存储已遍历的节点

2、初始阶段，将初始节点放入close，其他所有节点放入open

3、以初始节点为中心向外一层层遍历，获取离指定节点最近的子节点放入close并从新计算路径，直至close包含所有子节点

4. 用java怎么用迪杰斯特拉算有向图有权值的最短路径

Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式
用OPEN,CLOSE表的方式，其采用的是贪心法的算法策略，大概过程如下：
1.声明两个集合，open和close，open用于存储未遍历的节点，close用来存储已遍历的节点
2.初始阶段，将初始节点放入close，其他所有节点放入open
3.以初始节点为中心向外一层层遍历，获取离指定节点最近的子节点放入close并从新计算路径，直至close包含所有子节点

代码实例如下：
Node对象用于封装节点信息，包括名字和子节点
[java] view plain
public class Node {
private String name;
private Map<Node,Integer> child=new HashMap<Node,Integer>();
public Node(String name){
this.name=name;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Map<Node, Integer> getChild() {
return child;
}
public void setChild(Map<Node, Integer> child) {
this.child = child;
}
}

MapBuilder用于初始化数据源，返回图的起始节点
[java] view plain
public class MapBuilder {
public Node build(Set<Node> open, Set<Node> close){
Node nodeA=new Node("A");
Node nodeB=new Node("B");
Node nodeC=new Node("C");
Node nodeD=new Node("D");
Node nodeE=new Node("E");
Node nodeF=new Node("F");
Node nodeG=new Node("G");
Node nodeH=new Node("H");
nodeA.getChild().put(nodeB, 1);
nodeA.getChild().put(nodeC, 1);
nodeA.getChild().put(nodeD, 4);
nodeA.getChild().put(nodeG, 5);
nodeA.getChild().put(nodeF, 2);
nodeB.getChild().put(nodeA, 1);
nodeB.getChild().put(nodeF, 2);
nodeB.getChild().put(nodeH, 4);
nodeC.getChild().put(nodeA, 1);
nodeC.getChild().put(nodeG, 3);
nodeD.getChild().put(nodeA, 4);
nodeD.getChild().put(nodeE, 1);
nodeE.getChild().put(nodeD, 1);
nodeE.getChild().put(nodeF, 1);
nodeF.getChild().put(nodeE, 1);
nodeF.getChild().put(nodeB, 2);
nodeF.getChild().put(nodeA, 2);
nodeG.getChild().put(nodeC, 3);
nodeG.getChild().put(nodeA, 5);
nodeG.getChild().put(nodeH, 1);
nodeH.getChild().put(nodeB, 4);
nodeH.getChild().put(nodeG, 1);
open.add(nodeB);
open.add(nodeC);
open.add(nodeD);
open.add(nodeE);
open.add(nodeF);
open.add(nodeG);
open.add(nodeH);
close.add(nodeA);
return nodeA;
}
}
图的结构如下图所示：

Dijkstra对象用于计算起始节点到所有其他节点的最短路径
[java] view plain
public class Dijkstra {
Set<Node> open=new HashSet<Node>();
Set<Node> close=new HashSet<Node>();
Map<String,Integer> path=new HashMap<String,Integer>();//封装路径距离
Map<String,String> pathInfo=new HashMap<String,String>();//封装路径信息
public Node init(){
//初始路径,因没有A->E这条路径,所以path(E)设置为Integer.MAX_VALUE
path.put("B", 1);
pathInfo.put("B", "A->B");
path.put("C", 1);
pathInfo.put("C", "A->C");
path.put("D", 4);
pathInfo.put("D", "A->D");
path.put("E", Integer.MAX_VALUE);
pathInfo.put("E", "A");
path.put("F", 2);
pathInfo.put("F", "A->F");
path.put("G", 5);
pathInfo.put("G", "A->G");
path.put("H", Integer.MAX_VALUE);
pathInfo.put("H", "A");
//将初始节点放入close,其他节点放入open
Node start=new MapBuilder().build(open,close);
return start;
}
public void computePath(Node start){
Node nearest=getShortestPath(start);//取距离start节点最近的子节点,放入close
if(nearest==null){
return;
}
close.add(nearest);
open.remove(nearest);
Map<Node,Integer> childs=nearest.getChild();
for(Node child:childs.keySet()){
if(open.contains(child)){//如果子节点在open中
Integer newCompute=path.get(nearest.getName())+childs.get(child);
if(path.get(child.getName())>newCompute){//之前设置的距离大于新计算出来的距离
path.put(child.getName(), newCompute);
pathInfo.put(child.getName(), pathInfo.get(nearest.getName())+"->"+child.getName());
}
}
}
computePath(start);//重复执行自己,确保所有子节点被遍历
computePath(nearest);//向外一层层递归,直至所有顶点被遍历
}
public void printPathInfo(){
Set<Map.Entry<String, String>> pathInfos=pathInfo.entrySet();
for(Map.Entry<String, String> pathInfo:pathInfos){
System.out.println(pathInfo.getKey()+":"+pathInfo.getValue());
}
}
/**
* 获取与node最近的子节点
*/
private Node getShortestPath(Node node){
Node res=null;
int minDis=Integer.MAX_VALUE;
Map<Node,Integer> childs=node.getChild();
for(Node child:childs.keySet()){
if(open.contains(child)){
int distance=childs.get(child);
if(distance<minDis){
minDis=distance;
res=child;
}
}
}
return res;
}
}

Main用于测试Dijkstra对象
[java] view plain
public class Main {
public static void main(String[] args) {
Dijkstra test=new Dijkstra();
Node start=test.init();
test.computePath(start);
test.printPathInfo();
}
}

5. dijkstra算法有哪些

迪杰斯特拉算法用来解决从顶点v0出发到其余顶点的最短路径，该算法按照最短路径长度递增的顺序产生所以最短路径。

对于图G=（V，E），将图中的顶点分成两组：

第一组S：已求出的最短路径的终点集合（开始为{v0}）。

第二组V-S：尚未求出最短路径的终点集合（开始为V-{v0}的全部结点）。

算法将按最短路径长度的递增顺序逐个将第二组的顶点加入到第一组中，直到所有顶点都被加入到第一组顶点集S为止。

(5)迪杰斯特拉算法java扩展阅读：

从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，此时完成一个顶点，需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。 然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。

6. 矩阵怎么用来计算dijkstra算法 java

怎样用matlab编程实现Dijkstra算法
%单源点最短路径Dijkstra算法实现

function [d index1 index2] = Dijkf(a)

% a 表示图的权值矩阵

% d 表示所求最短路的权和

% index1 表示标号顶点顺序

% index2 表示标号顶点索引

%参数初始化

M= max(max(a));

pb(1:length(a))= 0; % 标记向量,表明是否已进入S集合

pb(1)= 1;

index1= 1;

index2= ones(1,length(a));

d(1:length(a))= M; % d矩阵所有元素都初始化为最大权值

d(1)= 0; % 以v1点为源点

temp= 1;

% 更新l(v),同时记录顶点顺序和顶点索引

while sum(pb)<length(a) % 重复步骤2,直到满足停止条件

tb= find(pb==0);

d(tb)= min(d(tb),d(temp)+a(temp,tb)); % 更新l(v)

tmpb= find(d(tb)==min(d(tb))); % 找出min(l(v))

temp= tb(tmpb(1));

pb(temp)= 1;

index1= [index1,temp]; % 记录标号顺序

index= index1(find(d(index1)==d(temp)-a(temp,index1)));

if length(index)>=2

index= index(1);

end % if结束

index2(temp)= index; % 记录标号索引

end % while结束

end

% Dijkf函数结束

7. 寻求大神帮忙写Java代码，要用Dijkstra’s algorithm（迪杰斯特拉算法）

package minRoad.no;

import java.util.Arrays;

//这个程序用来求得一个图的最短路径矩阵
public class ShortestDistance_V4 {
private static final int inf = Integer.MAX_VALUE;// 表示两个点之间无法直接连通

public static int[][] dijkstra(int[][] graph) {
int min, v, u = 0, n = graph.length;
int[] path = new int[n];
int[] dist = new int[n];
boolean[] s = new boolean[n];
Arrays.fill(s, false);
Arrays.fill(dist, inf);
for (int i = 0; i < n; i++) {
dist[i] = graph[u][i];
if (i != u && dist[i] < inf)
path[i] = u;
else
path[i] = -1;
}
s[u] = true;
while (true) {
min = inf;
v = -1;
// 找到最小的dist
for (int i = 0; i < n; i++) {
if (!s[i]) {
if (dist[i] < min) {
min = dist[i];
v = i;
}
}
}
if (v == -1) break;// 找不到更短的路径了
// 更新最短路径
s[v] = true;
for (int i = 0; i < n; i++) {
if (!s[i] && graph[v][i] != inf && dist[v] + graph[v][i] < dist[i]) {
dist[i] = dist[v] + graph[v][i];
path[i] = v;
}
}
}
// 输出路径
int[] shortest = new int[n];
for (int i = 1; i < n; i++) {
Arrays.fill(shortest, 0);
int k = 0;
shortest[k] = i;
while (path[shortest[k]] != 0) {
k++;
shortest[k] = path[shortest[k - 1]];
}
k++;
shortest[k] = 0;
}
int[] tmp = new int[shortest.length];
for (int i = 0; i < tmp.length; i++) {
tmp[i] = shortest[tmp.length - i - 1];
}
return new int[][] { dist, tmp };
}

/**
* <pre>
* v0
* 1, v1
* 4, 2, v2
* inf, 7, -1, v3
* inf, 5, 1, 3, v4
* inf, inf, inf, 2, 6, v5
* </pre>
*
* *
*
* <pre>
* A--------30------->D
* |\ ∧|
* | \ / |
* | \ / |
* | 10 10 |
* | \ / 20
* | \ / |
* | \ / |
* | ∨ / ∨
* 20 B E
* | / ∧
* | / /
* | / /
* | 5 /
* | / 30
* | / /
* | / /
* ∨∠ /
* C
* </pre>
*
* @param args
*/
public static void main(String[] args) {
int[][] W1 = {
{ 0, 10, 20, 30, inf },
{ 10, 0, 5, 10, inf },
{ 20, 5, 0, inf, 30 },
{ 30, 10, inf, 0, 20 },
{ inf, inf, 30, 20, 0 },
};
// http://sbp810050504.blog.51cto.com/2799422/690803
// http://sbp810050504.blog.51cto.com/2799422/1163565
// int[][] W = {
// { 0, 1, 4, inf, inf, inf },
// { 1, 0, 2, 7, 5, inf },
// { 4, 2, 0, inf, 1, inf },
// { inf, 7, inf, 0, 3, 2 },
// { inf, 5, 1, 3, 0, 6 },
// { inf, inf, inf, 2, 6, 0 }};
int[][] distAndShort = dijkstra(W1);
System.out.println(Arrays.toString(distAndShort[0]));
System.out.println(Arrays.toString(distAndShort[1]));
// distance: { 0, 1, 3, 7, 4, 9};
}
}

8. 求大佬用java帮我实现dijkstra算法，单源最短路径

python">
import heapq
from collections import defaultdict
edges = [["A","B"],["A","D"],["A","E"],["B","C"],["C","E"],["D","E"],["D","C"]]
dist = [10,30,100,50,10,60,20]
res = []
def dijkstra(e,dist,start,end):
‍  hm = defaultdict(list)
‍  for i in range(len(e)):
‍  ‍  hm[e[i][0]].append((e[i][1],dist[i]))
‍  r = {}
‍  r[start] = 0
‍  q = [(0,start,[start])]
‍  while q:
‍  ‍  dis,node,res = heapq.heappop(q)
‍  ‍  if node == end:
‍  ‍  ‍  return dis,res
‍  ‍  for u,v in hm[node]:
‍  ‍  ‍  t = dis+v
‍  ‍  ‍  if u not in r or t < r[u]:
‍  ‍  ‍  ‍  r[u] = t
‍  ‍  ‍  ‍  heapq.heappush(q,(t,u,res+[u]))
‍  return 0,[]
dijkstra(edges,dist,"A","E")

9. 解释一下dijkstra算法这个计算过程的意思 怎么算的

最近也看到这个算法，不过主要是通过C语言介绍的，不太一样，但基本思想差不多。下面只是我个人的看法不一定准确。
Dijkstra算法主要解决指定某点(源点)到其他顶点的最短路径问题。
基本思想：每次找到离源点最近的顶点，然后以该顶点为中心(过渡顶点)，最终找到源点到其余顶点的最短路。

t=1：令源点(v_0)的标号为永久标号(0,λ)(右上角加点), 其他为临时(+无穷,λ). 就是说v_0到v_0的距离是0，其他顶点到v_0的距离为+无穷。t=1时，例5.3上面的步骤(2)(3)并不能体现

t=2：第1步v_0(k=0)获得永久标号，记L_j为顶点标号当前的最短距离(比如v_0标号(0,λ)中L_0=0), 边(v_k,v_j)的权w_kj. 步骤(2)最关键，若v_0与v_j之间存在边，则比较L_k+w_kj与L_j, 而L_k+w_kj=L_0+w_0j<L_j=+无穷。
这里只有v_1,v_2与v_0存在边，所以当j=1,2时修改标号, 标号分别为(L_1, v_0)=(1, v_0), (L_2, v_0)=(4, v_0), 其他不变。步骤(3)比较所有临时标号中L_j最小的顶点, 这里L_1=1最小，v_1获得永久标号(右上角加点)。

t=3: 第2步中v_1获得永久标号(k=1), 同第2步一样，通过例5.3上面的步骤(2)(3)，得到永久标号。 步骤(2),若v_1与v_j(j=2,3,4,5(除去获得永久标号的顶点))之间存在边，则比较L_1+w_1j与L_j。这里v_1与v_2，v_3，v_,4存在边，
对于v_2, L_1+w_12=1+2=3<L_2=4, 把v_2标号修改为(L_1+w_12, v_1)=(3, v_1);
对于v_3, L_1+w_13=1+7=8<L_3=+无穷, 把v_3标号修改为(L_1+w_13, v_1)=(8, v_1);
对于v_4, L_1+w_14=1+5=6<L_4=+无穷, 把v_4标号修改为(L_1+w_14, v_1)=(6, v_1);
v_5与v_1不存在边，标号不变。步骤(3), 找这些标号L_j最小的顶点，这里v_2标号最小

t=4: k=2, 与v_2存在边的未获得永久标号的顶点只有v_4, 比较L_2+w_24=3+1=4<L_4=6, 把v_4标号修改为(L_2+w_24, v_2)=(4, v_2); 其他不变。步骤(3), L_4=4最小。

t=5: k=4, 同理先找v_4邻接顶点，比较，修改标号，找L_j最小
t=6: 同理

啰嗦的这么多，其实步骤(2)是关键，就是通过比较更新最短路径，右上角标点的就是距离源点最近的顶点，之后每一步就添加一个新的”源点”，再找其他顶点与它的最短距离。

迪杰斯特拉算法(Dijkstra)(网络)：
http://ke..com/link?url=gc_mamV4z7tpxwqju6BoqxVOZ_josbPNcGKtLYJ5GJsJT6U28koc_#4
里面有个动图，更形象地说明了该算法的过程。(其中每次标注的一个红色顶点out就和你的这本书中获得永久标号是相似的)

10. 迪杰斯特拉算法能用html或者jsp连接数据库展现出来吗

首先答案是可以，不过这里面涉及到很多的程序知识。jsp直接连数据库是没有问题，但html是不可以直接连接数据库的，必须通过程序后端进行连接。涉及知识点有数据库，jdbc，java，jsp，js等等。