您的位置:

包含dijkstra可视化java的词条

本文目录一览:

求大佬用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 = {}

  r = 0

  q = [(0,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")

矩阵怎么用来计算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算法实现最短路问题,要用图形用户界面体现出来,动态静态都行

巧了,前两天做课程设计,刚做完,不知道你现在还要吗,要的话加QQ;272614124

声明:界面上的路径是画出来的,结果是同TextField输出的

跪求解释java中shortestpath.DijkstraDistance的具体用法????

//这个算法用来解决无向图中任意两点的最短路径  

public class ShortestDistanceOfTwoPoint_V5 {  

    public static int dijkstra(int[][] W1, int start, int end) {  

        boolean[] isLabel = new boolean[W1[0].length];// 是否标号  

        int[] indexs = new int[W1[0].length];// 所有标号的点的下标集合,以标号的先后顺序进行存储,实际上是一个以数组表示的栈  

        int i_count = -1;//栈的顶点  

        int[] distance = W1.clone();// v0到各点的最短距离的初始值  

        int index = start;// 从初始点开始  

        int presentShortest = 0;//当前临时最短距离  

 

        indexs[++i_count] = index;// 把已经标号的下标存入下标集中  

        isLabel[index] = true;  

          

        while (i_countW1[0].length) {  

            // 第一步:标号v0,即w[0][0]找到距离v0最近的点  

 

            int min = Integer.MAX_VALUE;  

            for (int i = 0; i  distance.length; i++) {  

                if (!isLabel[i]  distance[i] != -1  i != index) {  

                    // 如果到这个点有边,并且没有被标号  

                    if (distance[i]  min) {  

                        min = distance[i];  

                        index = i;// 把下标改为当前下标  

                    }  

                }  

            }  

            if (index == end) {//已经找到当前点了,就结束程序  

                break;  

            }  

            isLabel[index] = true;//对点进行标号  

            indexs[++i_count] = index;// 把已经标号的下标存入下标集中  

            if (W1[indexs[i_count - 1]][index] == -1 

                    || presentShortest + W1[indexs[i_count - 1]][index]  distance[index]) {  

                // 如果两个点没有直接相连,或者两个点的路径大于最短路径  

                presentShortest = distance[index];  

            } else {  

                presentShortest += W1[indexs[i_count - 1]][index];  

            }  

 

            // 第二步:将distance中的距离加入vi  

            for (int i = 0; i  distance.length; i++) {  

                // 如果vi到那个点有边,则v0到后面点的距离加  

                if (distance[i] == -1  W1[index][i] != -1) {// 如果以前不可达,则现在可达了  

                    distance[i] = presentShortest + W1[index][i];  

                } else if (W1[index][i] != -1 

                         presentShortest + W1[index][i]  distance[i]) {  

                    // 如果以前可达,但现在的路径比以前更短,则更换成更短的路径  

                    distance[i] = presentShortest + W1[index][i];  

                }  

 

            }  

        }  

        //如果全部点都遍历完,则distance中存储的是开始点到各个点的最短路径  

        return distance - distance;  

    }  

    public static void main(String[] args) {  

        // 建立一个权值矩阵  

        int[][] W1 = { //测试数据1  

                { 0, 1, 4, -1, -1, -1 },  

                { 1, 0, 2, 7, 5, -1 },  

                { 4, 2, 0, -1, 1, -1 },   

                { -1, 7, -1, 0, 3, 2 },  

                { -1, 5, 1, 3, 0, 6 },   

                { -1, -1, -1, 2, 6, 0 } };  

        int[][] W = { //测试数据2  

                { 0, 1, 3, 4 },  

                { 1, 0, 2, -1 },  

                { 3, 2, 0, 5 },  

                { 4, -1, 5, 0 } };  

 

        System.out.println(dijkstra(W1, 0,4));  

 

    }  

}

一个有关于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;

}

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

}

}

}

}