dijstrajava的简单介绍

admin 2023-03-18 21:07:09 273

本篇文章给大家谈谈dijstrajava，以及对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

1、矩阵怎么用来计算dijkstra算法 java
2、用java怎么用迪杰斯特拉算有向图有权值的最短路径
3、求大佬用java帮我实现dijkstra算法，单源最短路径
4、寻求大神帮忙写Java代码，要用Dijkstra’s algorithm（迪杰斯特拉算法）
5、一个有关于java的算法问题，求高手协做

矩阵怎么用来计算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函数结束

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

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

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

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

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

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

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

代码实例如下：

Node对象用于封装节点信息，包括名字和子节点

[java] view plain copy

public class Node {

private String name;

private MapNode,Integer child=new HashMapNode,Integer();

public Node(String name){

this.name=name;

}

public String getName() {

return name;

}

public void setName(String name) {

this.name = name;

}

public MapNode, Integer getChild() {

return child;

}

public void setChild(MapNode, Integer child) {

this.child = child;

}

MapBuilder用于初始化数据源，返回图的起始节点

[java] view plain copy

public class MapBuilder {

public Node build(SetNode open, SetNode 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 copy

public class Dijkstra {

SetNode open=new HashSetNode();

SetNode close=new HashSetNode();

MapString,Integer path=new HashMapString,Integer();//封装路径距离

MapString,String pathInfo=new HashMapString,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);

MapNode,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(){

SetMap.EntryString, String pathInfos=pathInfo.entrySet();

for(Map.EntryString, String pathInfo:pathInfos){

System.out.println(pathInfo.getKey()+":"+pathInfo.getValue());

}

/**

* 获取与node最近的子节点

private Node getShortestPath(Node node){

Node res=null;

int minDis=Integer.MAX_VALUE;

MapNode,Integer childs=node.getChild();

for(Node child:childs.keySet()){

if(open.contains(child)){

int distance=childs.get(child);

if(distanceminDis){

minDis=distance;

res=child;

}

return res;

}

Main用于测试Dijkstra对象

[java] view plain copy

public class Main {

public static void main(String[] args) {

Dijkstra test=new Dijkstra();

Node start=test.init();

test.computePath(start);

test.printPathInfo();

}

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

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 = {}

本篇文章给大家谈谈dijstrajava，以及对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

= 0

q = [(0,start,

本篇文章给大家谈谈dijstrajava，以及对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

)]

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")

寻求大神帮忙写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 },

};

// 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};

}

一个有关于java的算法问题，求高手协做

//参考别人的,自己就懒得写了,你拿去参考参考...

import java.util.ArrayList;

import java.util.HashMap;

import java.util.HashSet;

import java.util.List;

import java.util.Map;

import java.util.Set;

public class Dijkstra {

private int[][] graph;// 加权有向图

private int start;// 源点编号从 0开始

private int dimention;

static int INF = Integer.MAX_VALUE / 100;

// 用于标记顶点是否已经计算

private SetInteger vertexSet = new HashSetInteger();

// 存储结果，Map的key对应各终点编号，value对应路径编号列表。

private MapInteger, ListInteger pathListMap = new HashMapInteger, ListInteger();

public Dijkstra(int[][] graph, int start) {

this.graph = graph;

this.start = start;

this.dimention = graph.length;

calculate();

}

private void calculate() {

// 初始化

for (int end = 0; end dimention; end++) {

if (end == start) {

continue;

}// 起始点自己的路径排除。

ListInteger pathList = new ArrayListInteger();

pathList.add(start);// 每条路径的起始点都为start，pathList只记录编号，不记录路径权值

pathList.add(end);// 每条路径的第二个参数为终点编号

pathListMap.put(end, pathList);

}

// 计算主体

for (int bridge = 0; bridge dimention; bridge++) {

if (bridge == start) {

continue;

}

if (!vertexSet.contains(bridge)) {// 确保每个基点只循环计算一次

for (int next = 0; next dimention; next++) {

if (next == start || next == bridge) {

continue;

}

if (startTo(bridge) + getRawLength(bridge, next) startTo(next)) {

ListInteger pathList = pathListMap.get(next);

ListInteger bridgePathList = pathListMap.get(bridge);

// 清空，使用新的

pathList.clear();

pathList.addAll(bridgePathList);

pathList.add(next);

}

vertexSet.add(bridge);

}

// 检查，是否桥接的路径都被更新

for (int end = 0; end dimention; end++) {

if (end == start) {

continue;

}

ListInteger pathList = pathListMap.get(end);

int size = pathList.size();

if (size 2) {

for (int end2 = 0; end2 dimention; end2++) {

int isEnd = pathList.get(size - 2);

if (end2 == isEnd) {

pathList.clear();

pathList.addAll(pathListMap.get(end2));

pathList.add(end);

}

private int startTo(int end) {

int pathLen = 0;

ListInteger pathList = pathListMap.get(end);

for (int i = 0; i pathList.size() - 1; i++) {

pathLen += graph[pathList.get(i)][pathList.get(i + 1)];

}

return pathLen;

}

private int getRawLength(int start, int end) {

if (end == start) {

return 0;

}

return graph

本篇文章给大家谈谈dijstrajava，以及对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

关于dijstrajava和的介绍到此就结束了，不知道你从中找到你需要的信息了吗？如果你还想了解更多这方面的信息，记得收藏关注本站。

;

}

public int getLength(int end) {

if (end == start) {

return 0;

}

return startTo(end);

}

public void printResult() {

System.out.println(pathListMap);

}

public MapInteger, ListInteger getPathListMap() {

return pathListMap;

}

public static void main(String[] args) {

* int [][] graph = { { INF, 10, INF, 30, 100}, { INF, INF, 50, INF,

* INF}, { INF, INF, INF, INF, 10}, { INF, INF, 20, INF, 60}, { INF,

* INF, INF, INF, INF}};

int[][] graph = { { INF, INF, 10, INF, 30, 100 },

{ INF, INF, 5, INF, INF, INF },

{ INF, INF, INF, 50, INF, INF },

{ INF, INF, INF, INF, INF, 10 },

{ INF, INF, INF, 20, INF, 60 },

{ INF, INF, INF, INF, INF, INF }, };

int start = 0;

int end = 0;

int length = graph.length;

for (start = 0; start length; start++) {

System.out.println();

Dijkstra dijkstra = new Dijkstra(graph, start);

dijkstra.printResult();

for (end = 0; end length; end++) {

if (end == start) {

continue;

}

int len = dijkstra.getLength(end);

System.out.println(" Length(" + start + "-" + end + ") = "

+ ((len == INF) ? "Infinity" : len));

}

关于dijstrajava和的介绍到此就结束了，不知道你从中找到你需要的信息了吗？如果你还想了解更多这方面的信息，记得收藏关注本站。

标签：dijstrajava