单源路径算法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")

相关问答

Q1: 怎么用c语言实现单源最短路径问题？要求是用Dijkstra算法，最好写出所有的代码，包括结构定义等等，对一

C语言代码：//清华大学出版社光盘的代码

void ShortestPath_DIJ(MGraph G,int v0,PathMatrix P,ShortPathTable D)

{ // 算法7.15

// 用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]

// 及其带权长度D[v]。

// 若P[v][w]为TRUE，则w是从v0到v当前求得最短路径上的顶点。

// final[v]为TRUE当且仅当v∈S,即已经求得从v0到v的最短路径。

int i=0,j, v,w,min;

bool final[MAX_VERTEX_NUM];

for (v=0; vG.vexnum; ++v) {

final[v] = FALSE;

D[v] = G.arcs[v0][v].adj;

for (w=0; wG.vexnum; ++w) P[v][w] = FALSE; // 设空路径

if (D[v] INFINITY) { P[v][v0] = TRUE; P[v][v] = TRUE; }

}

D[v0] = 0; final[v0] = TRUE; // 初始化，v0顶点属于S集

//--- 开始主循环，每次求得v0到某个v顶点的最短路径，并加v到S集 ---

for (i=1; iG.vexnum; ++i) { // 其余G.vexnum-1个顶点

min = INFINITY; // 当前所知离v0顶点的最近距离

for (w=0; wG.vexnum; ++w)

if (!final[w]) // w顶点在V-S中

if (D[w]min) { v = w; min = D[w]; } // w顶点离v0顶点更近

final[v] = TRUE; // 离v0顶点最近的v加入S集

for (w=0; wG.vexnum; ++w) // 更新当前最短路径及距离

if (!final[w] (min+G.arcs[v][w].adjD[w])) {

// 修改D[w]和P[w], w∈V-S

D[w] = min + G.arcs[v][w].adj;

for(j=0;jG.vexnum;j++) P[w][j] = P[v][j]; //第v行赋值于第w行

P[w][w] = TRUE; // P[w] = P[v]+[w]

}//if

}//for

} // ShortestPath_DIJ

Q2: 单源最短路径的完整代码及其迭代过程

一本书上的练习题,刚编的.注释用的日文字体,看不懂记得提问.

import java.util.*;

public class Search {

Node node[];

Node start;

Node goal;

Search() {

makeStateSpace();

}

private void makeStateSpace() {

node = new Node[10];

// 状态空间の生成

node[0] = new Node("L.A.Airport", 0);

start = node[0];

node[1] = new Node("UCLA", 7);

node[2] = new Node("Hollywood", 4);

node[3] = new Node("Anaheim", 6);

node[4] = new Node("Grand Canyon", 1);

node[5] = new Node("SanDiego", 2);

node[6] = new Node("Downtown", 3);

node[7] = new Node("Pasadena", 4);

node[8] = new Node("DisneyLand", 2);

node[9] = new Node("Las Vegas", 0);

goal = node[9];

node[0].addChild(node[1], 1);

node[0].addChild(node[2], 3);

node[1].addChild(node[2], 1);

node[1].addChild(node[6], 6);

node[2].addChild(node[3], 6);

node[2].addChild(node[6], 6);

node[2].addChild(node[7], 3);

node[3].addChild(node[4], 5);

node[3].addChild(node[7], 2);

node[3].addChild(node[8], 4);

node[4].addChild(node[8], 2);

node[4].addChild(node[9], 1);

node[5].addChild(node[1], 1);

node[6].addChild(node[5], 7);

node[6].addChild(node[7], 2);

node[7].addChild(node[8], 1);

node[7].addChild(node[9], 7);

node[8].addChild(node[9], 5);

}

/***

* 幅优先探索

public void breadthFirst() {

ListNode open = new ArrayListNode();

open.add(start);

ListNode closed = new ArrayListNode();

boolean success = false;

int step = 0;

for (;;) {

System.out.println("STEP:" + (step++));

System.out.println("OPEN:" + open.toString());

System.out.println("CLOSED:" + closed.toString());

// openは空か？

if (open.size() == 0) {

success = false;

break;

} else {

// openの先头を取り出し node とする．

Node node = open.get(0);

open.remove(0);

// node はゴールか？

if (node == goal) {

success = true;

break;

} else {

// node を展开して子节点をすべて求める．

ArrayListNode children = node.getChildren();

// node を closed に入れる．

closed.add(node);

// 子节点 m が open にも closed にも含まれていなければ，

for (int i = 0; i children.size(); i++) {

Node m = (Node) children.get(i);

if (!open.contains(m) !closed.contains(m)) {

// m から node へのポインタを付ける．

m.setPointer(node);

if (m == goal) {

open.add(0, m);

} else {

open.add(m);

}

if (success) {

System.out.println("*** Solution ***");

printSolution(goal);

}

/***

* 深さ优先探索

public void depthFirst() {

ListNode open = new ArrayListNode();

open.add(start);

ListNode closed = new ArrayListNode();

boolean success = false;

int step = 0;

for (;;) {

System.out.println("STEP:" + (step++));

System.out.println("OPEN:" + open.toString());

System.out.println("CLOSED:" + closed.toString());

// openは空か？

if (open.size() == 0) {

success = false;

break;

} else {

// openの先头を取り出し node とする．

Node node = open.get(0);

open.remove(0);

// node はゴールか？

if (node == goal) {

success = true;

break;

} else {

// node を展开して子节点をすべて求める．

ArrayListNode children = node.getChildren();

// node を closed に入れる．

closed.add(node);

// 子节点 m が open にも closed にも含まれていなければ，

// 以下を実行．幅优先探索と异なるのはこの部分である．

// j は复数の子节点を适切にopenの先头に置くために位置

// を调整する変数であり，一般には展开したときの子节点

// の位置は任意でかまわない．

int j = 0;

for (int i = 0; i children.size(); i++) {

Node m = (Node) children.get(i);

if (!open.contains(m) !closed.contains(m)) {

// m から node へのポインタを付ける

m.setPointer(node);

if (m == goal) {

open.add(0, m);

} else {

open.add(j, m);

}

j++;

}

if (success) {

System.out.println("*** Solution ***");

printSolution(goal);

}

/***

* 分岐限定法

public void branchAndBound() {

ListNode open = new ArrayListNode();

open.add(start);

start.setGValue(0);

ListNode closed = new ArrayListNode();

boolean success = false;

int step = 0;

for (;;) {

System.out.println("STEP:" + (step++));

System.out.println("OPEN:" + open.toString());

System.out.println("CLOSED:" + closed.toString());

// openは空か？

if (open.size() == 0) {

success = false;

break;

} else {

// openの先头を取り出し node とする．

Node node = open.get(0);

open.remove(0);

// node はゴールか？

if (node == goal) {

success = true;

break;

} else {

// node を展开して子节点をすべて求める．

ListNode children = node.getChildren();

// node を closed に入れる．

closed.add(node);

for (int i = 0; i children.size(); i++) {

Node m = (Node) children.get(i);

// 子节点mがopenにもclosedにも含まれていなければ，

if (!open.contains(m) !closed.contains(m)) {

// m から node へのポインタを付ける．

m.setPointer(node);

// nodeまでの评価値とnode-mのコストを

// 足したものをmの评価値とする

int gmn = node.getGValue() + node.getCost(m);

m.setGValue(gmn);

open.add(m);

}

// 子节点mがopenに含まれているならば，

if (open.contains(m)) {

int gmn = node.getGValue() + node.getCost(m);

if (gmn m.getGValue()) {

m.setGValue(gmn);

m.setPointer(node);

}

open = sortUpperByGValue(open);

}

if (success) {

System.out.println("*** Solution ***");

printSolution(goal);

}

/***

* 山登り法

public void hillClimbing() {

start.setGValue(0);

boolean success = false;

// Start を node とする．

Node node = start;

for (;;) {

// node はゴールか？

if (node == goal) {

success = true;

break;

} else {

// node を展开して子节点をすべて求める．

ArrayListNode children = node.getChildren();

System.out.println(children.toString());

for (int i = 0; i children.size(); i++) {

Node m = children.get(i);

// m から node へのポインタを付ける．

m.setPointer(node);

}

// 子节点の中に goal があれば goal を node とする．

// なければ，最小の hValue を持つ子节点 m を node

// とする．

boolean goalp = false;

Node min = children.get(0);

for (int i = 0; i children.size(); i++) {

Node a = children.get(i);

if (a == goal) {

goalp = true;

} else if (min.getHValue() a.getHValue()) {

min = a;

}

if (goalp) {

node = goal;

} else {

node = min;

}

if (success) {

System.out.println("*** Solution ***");

printSolution(goal);

}

/***

* 最良优先探索

public void bestFirst() {

ListNode open = new ArrayListNode();

open.add(start);

ListNode closed = new ArrayListNode();

boolean success = false;

int step = 0;

for (;;) {

System.out.println("STEP:" + (step++));

System.out.println("OPEN:" + open.toString());

System.out.println("CLOSED:" + closed.toString());

// openは空か？

if (open.size() == 0) {

success = false;

break;

} else {

// openの先头を取り出し node とする．

Node node = open.get(0);

open.remove(0);

// node はゴールか？

if (node == goal) {

success = true;

break;

} else {

// node を展开して子节点をすべて求める．

ListNode children = node.getChildren();

// node を closed に入れる．

closed.add(node);

for (int i = 0; i children.size(); i++) {

Node m = (Node) children.get(i);

// 子节点mがopenにもclosedにも含まれていなければ，

if (!open.contains(m) !closed.contains(m)) {

// m から node へのポインタを付ける．

m.setPointer(node);

open.add(m);

}

open = sortUpperByHValue(open);

}

if (success) {

System.out.println("*** Solution ***");

printSolution(goal);

}

/***

* A* アルゴリズム

public void aStar() {

ListNode open = new ArrayListNode();

open.add(start);

start.setGValue(0);

start.setFValue(0);

ListNode closed = new ArrayListNode();

boolean success = false;

int step = 0;

for (;;) {

System.out.println("STEP:" + (step++));

System.out.println("OPEN:" + open.toString());

System.out.println("CLOSED:" + closed.toString());

// openは空か？

if (open.size() == 0) {

success = false;

break;

} else {

// openの先头を取り出し node とする．

Node node = open.get(0);

open.remove(0);

// node はゴールか？

if (node == goal) {

success = true;

break;

} else {

// node を展开して子节点をすべて求める．

ListNode children = node.getChildren();

// node を closed に入れる．

closed.add(node);

for (int i = 0; i children.size(); i++) {

Node m = children.get(i);

int gmn = node.getGValue() + node.getCost(m);

int fmn = gmn + m.getHValue();

// 各子节点mの评価値とポインタを设定する

if (!open.contains(m) !closed.contains(m)) {

// 子节点mがopenにもclosedにも含まれていない场合

// m から node へのポインタを付ける．

m.setGValue(gmn);

m.setFValue(fmn);

m.setPointer(node);

// mをopenに追加

open.add(m);

} else if (open.contains(m)) {

// 子节点mがopenに含まれている场合

if (gmn m.getGValue()) {

// 评価値を更新し，m から node へのポインタを付け替える

m.setGValue(gmn);

m.setFValue(fmn);

m.setPointer(node);

}

} else if (closed.contains(m)) {

if (gmn m.getGValue()) {

// 子节点mがclosedに含まれていて fmn fm となる场合

// 评価値を更新し，mからnodeへのポインタを付け替える

m.setGValue(gmn);

m.setFValue(fmn);

m.setPointer(node);

// 子节点mをclosedからopenに移动

closed.remove(m);

open.add(m);

}

open = sortUpperByFValue(open);

}

if (success) {

System.out.println("*** Solution ***");

printSolution(goal);

}

/***

* 解の表示

public void printSolution(Node theNode) {

if (theNode == start) {

System.out.println(theNode.toString());

} else {

System.out.print(theNode.toString() + " - ");

printSolution(theNode.getPointer());

}

/***

* Vector を Node の fValue の升顺（小さい顺）に列べ换える．

public ListNode sortUpperByFValue(ListNode theOpen) {

ListNode newOpen = new ArrayListNode();

Node min, tmp = null;

while (theOpen.size() 0) {

min = (Node) theOpen.get(0);

for (int i = 1; i theOpen.size(); i++) {

tmp = (Node) theOpen.get(i);

if (min.getFValue() tmp.getFValue()) {

min = tmp;

}

newOpen.add(min);

theOpen.remove(min);

}

return newOpen;

}

/***

* Vector を Node の gValue の升顺（小さい顺）に列べ换える．

public ListNode sortUpperByGValue(ListNode theOpen) {

ListNode newOpen = new ArrayListNode();

Node min = null, tmp = null;

while (theOpen.size() 0) {

min = theOpen.get(0);

for (int i = 1; i theOpen.size(); i++) {

tmp = theOpen.get(i);

if (min.getGValue() tmp.getGValue()) {

min = tmp;

}

newOpen.add(min);

theOpen.remove(min);

}

return newOpen;

}

/***

* Vector を Node の hValue の升顺（小さい顺）に列べ换える．

public ListNode sortUpperByHValue(ListNode theOpen) {

ListNode newOpen = new ArrayListNode();

Node min, tmp = null;

while (theOpen.size() 0) {

min = (Node) theOpen.get(0);

for (int i = 1; i theOpen.size(); i++) {

tmp = (Node) theOpen.get(i);

if (min.getHValue() tmp.getHValue()) {

min = tmp;

}

newOpen.add(min);

theOpen.remove(min);

}

return newOpen;

}

public static void main(String args[]) {

Scanner in = new Scanner(System.in);

String s = in.next();

if (s.length() != 1) {

System.out.println("USAGE:");

System.out.println("java Search [Number]");

System.out.println("[Number] = 1 : Bredth First Search");

System.out.println("[Number] = 2 : Depth First Search");

System.out.println("[Number] = 3 : Branch and Bound Search");

System.out.println("[Number] = 4 : Hill Climbing Search");

System.out.println("[Number] = 5 : Best First Search");

System.out.println("[Number] = 6 : A star Algorithm");

} else {

int which = Integer.parseInt(s);

switch (which) {

case 1:

// 幅优先探索

System.out.println("\nBreadth First Search");

(new Search()).breadthFirst();

break;

case 2:

// 深さ优先探索

System.out.println("\nDepth First Search");

(new Search()).depthFirst();

break;

case 3:

// 分岐限定法

System.out.println("\nBranch and Bound Search");

(new Search()).branchAndBound();

break;

case 4:

// 山登り法

System.out.println("\nHill Climbing Search");

(new Search()).hillClimbing();

break;

case 5:

// 最良优先探索

System.out.println("\nBest First Search");

(new Search()).bestFirst();

break;

case 6:

// A*アルゴリズム

System.out.println("\nA star Algorithm");

(new Search()).aStar();

break;

default:

System.out.println("Please input numbers 1 to 6");

}

class Node {

String name;

ArrayListNode children;

MapNode, Integer childrenCosts;

Node pointer; // 解表示のためのポインタ

int gValue; // コスト

int hValue; // ヒューリスティック値

int fValue; // 评価値

boolean hasGValue = false;

boolean hasFValue = false;

Node(String theName, int theHValue) {

name = theName;

children = new ArrayListNode();

childrenCosts = new HashMapNode, Integer();

hValue = theHValue;

}

public String getName() {

return name;

}

public void setPointer(Node theNode) {

this.pointer = theNode;

}

public Node getPointer() {

return this.pointer;

}

public int getGValue() {

return gValue;

}

public void setGValue(int theGValue) {

hasGValue = true;

this.gValue = theGValue;

}

public int getHValue() {

return hValue;

}

public int getFValue() {

return fValue;

}

public void setFValue(int theFValue) {

hasFValue = true;

this.fValue = theFValue;

}

/***

* theChild この节点の子节点 theCost その子节点までのコスト

public void addChild(Node theChild, int theCost) {

children.add(theChild);

childrenCosts.put(theChild, theCost);

}

public ArrayListNode getChildren() {

return children;

}

public int getCost(Node theChild) {

return ((Integer) childrenCosts.get(theChild)).intValue();

}

public String toString() {

String result = name + "(h:" + hValue + ")";

if (hasGValue) {

result = result + "(g:" + gValue + ")";

}

if (hasFValue) {

result = result + "(f:" + fValue + ")";

}

return result;

}

Q3: 求java实现矩阵图上任意两点的最短路径源码

我用的是递归调用方法，有个小问题就是在打印步数的时候是返向的，原因是就是程序不断的调用自己，到最后判断基值位准退出调用。这才开始从栈里取出方法进行执行的原因。

代码欣赏：

public static int step = 1;

public static StringBuffer printStep = new StringBuffer();

public static int[][] maze ={{1,1,1,1,1,1,1,1,1,1,1},

{1,0,1,0,1,0,0,0,0,0,1 },

{1,0,1,0,0,0,1,0,1,1,1 },

{1,0,0,0,1,0,1,0,0,0,1 },

{1,0,1,1,0,0,1,0,0,1,1 },// 0代表可以通过，1代表不可通过

{1,0,1,0,1,1,0,1,0,0,1 },

{1,0,0,0,0,0,0,0,1,0,1 },

{1,0,1,0,1,0,1,0,1,0,1 },

{1,0,0,1,0,0,1,0,1,0,1 },

{1,1,1,1,1,1,1,1,1,1,1 } };

public static void main(String[] args) {

int i, j; //循环记数变量

Sample.way(1, 1);//二维数组起始值从下标1，1开始

System.out.println("起点从坐标 x = 1, y = 1开始");

System.out.println("终点坐标是 x = 8, y = 9结束");

System.out.println("这是迷宫图表");

System.out.println(" 0 1 2 3 4 5 6 7 8 9 10");

System.out.println(" +---+---+---+---+---+---+---+---+---+---+---+---+---+");

for(i = 0; i 10; i++){

System.out.print(" " + i + "‖");

for(j = 0; j 11; j++)

System.out.print("-" + maze[i][j] + "-‖");

System.out.println("");

System.out.println(" +---+---+---+---+---+---+---+---+---+---+---+---+---+");

}

//打印显示步数

System.out.print(printStep.toString());

}

public static boolean way(int x, int y){

if(maze[8][9] == 2)//代表递归终止条件（也就是当走出出口时标记为 2）

return true;

else{

if(maze[y][x] == 0){

maze[y][x] = 2;

* 下面if判断条件代表当前坐标为基点，

* 根据判断对当前位置进行递归调用：如：

* 往上、往右上、往右、往右下、往下、

* 往左下、往左、往左上的坐标是否可走，

* 判断是否可走的返回条件是：

* 2代表可通过、1代表不能通过、3表示已经走过，但是未能走通。

if(way(x, y - 1)){