老師有一個題:

使用狄克斯屈拉(Dikjstra)標號算法可得出解:

我用Java來實現了一下這個算法:

package test;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.HashSet;

import java.util.List;

import java.util.Set;

import lombok.Data;

public class MinRoute {

public static void main(String args[]) {

List edges=initGraph();

//查找從v1到v7的最短路長及最短路線

findMinDistance("1","7",edges);

}

public static List findMinDistance(String from,String to,List edges){

Vertex fromVertex=findVertex(from,edges);

fromVertex.setMinLen(0);

Set passedEdge=new HashSet();

System.out.print("find path:"+fromVertex.getName()+"->");

Vertex findVertex=recursionFindMinEdge(fromVertex.getName(),edges,passedEdge);

while(findVertex!=null&&!findVertex.getName().equals(to)) {

System.out.print(findVertex.getName()+"->");

findVertex=recursionFindMinEdge(findVertex.getName(),edges,passedEdge);

}

if(findVertex!=null&&findVertex.getName().equals(to)) {

System.out.println(findVertex.getName());

System.out.println("find! the minPath is:");

StringBuffer sb=new StringBuffer();

sb.append(findVertex.getName()+" > ");

Vertex minFromVertex=findVertex.getMinFrom();

while(!minFromVertex.getName().equals(from)) {

sb.append(minFromVertex.getName()+" > ");

minFromVertex=minFromVertex.getMinFrom();

}

sb.append(from);

System.out.println(sb.reverse().toString());

}else {

System.out.println("not find!");

}

return null;

}

private static Vertex recursionFindMinEdge(String from,List edges,Set passedEdge) {

Vertex fromVertex=findVertex(from, edges);

//查出以當前頂點為始點的，且始點未標號的邊

List fromEdges=findFromEdge(from,edges);

for(Edge edge:fromEdges) {

Integer oldMinLen=edge.getMinLen();

if(oldMinLen==null) {

edge.setMinLen(edge.getLen()+fromVertex.getMinLen());

}

}

passedEdge.addAll(fromEdges);

//查出之前走過的，且始點未標號的邊。找到最小路徑的邊，并設置其終點的minLen

Edge minLenEdge=null;

for(Edge edge:passedEdge) {

if(edge.getTo().getMinLen()!=null) {

continue;

}

if(minLenEdge==null||edge.getMinLen()

minLenEdge=edge;

}

}

Vertex findTargetVertex=minLenEdge.getTo();

findTargetVertex.setMinLen(minLenEdge.getMinLen());

findTargetVertex.setMinFrom(minLenEdge.getFrom());

return findTargetVertex;

}

/**

* 初始化圖

* @return 返回所有邊

*/

private static List initGraph() {

Vertex v1=new Vertex("1");

Vertex v2=new Vertex("2");

Vertex v3=new Vertex("3");

Vertex v4=new Vertex("4");

Vertex v5=new Vertex("5");

Vertex v6=new Vertex("6");

Vertex v7=new Vertex("7");

List rst=Arrays.asList(

new Edge(v1,v2, 8),

new Edge(v1,v3, 6),

new Edge(v1,v4, 2),

new Edge(v2,v5, 5),

new Edge(v3,v6, 4),

new Edge(v3,v4, 2),

new Edge(v3,v2, 5),

new Edge(v4,v3, 3),

new Edge(v4,v6, 2),

new Edge(v5,v7, 5),

new Edge(v6,v2, 3),

new Edge(v6,v5, 10),

new Edge(v6,v7, 7)

);

return rst;

}

private static Vertex findVertex(String name,List edges) {

for(Edge edge:edges) {

if(edge.getFrom().getName().equals(name)) {

return edge.getFrom();

}else if(edge.getTo().getName().equals(name)){

return edge.getTo();

}

}

return null;

}

private static List findFromEdge(String name,List edges) {

List findEdges=new ArrayList();

for(Edge edge:edges) {

if(edge.getFrom().getName().equals(name)) {

findEdges.add(edge);

}

}

return findEdges;

}

}

//有向圖始點

@Data

class Vertex{

private String name;

//臨時變量，一次計算時從起點到這點的最小距離

private Integer minLen;

//臨時變量，當得到最短路徑時，記錄上一個頂點

private Vertex minFrom;

public Vertex(String name) {

this.name=name;

}

}

@Data

class Edge{

private Vertex from;

private Vertex to;

//距離

private Integer len;

//臨時變量，一次計算時從起點到"to"點的最小距離

private Integer minLen;

public Edge(Vertex from,Vertex to,Integer len) {

this.from=from;

this.to=to;

this.len=len;

}

}

最后打印結果:

find path:1->4->6->3->2->7

find! the minPath is:

1 > 4 > 6 > 7

總結

以上是生活随笔為你收集整理的java找图最短路径_查找有向图最短路径的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。