本文介绍了Dijkstra算法在Java中的实现的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
} }
这是Djikstra算法在java中的实现，我从书中引入了算法。但是在某些情况下结果不准确。对于下面的图，输出显示顶点F距离源顶点A的最小距离作为16，实际上是12.我算法相当新，所以任何改善代码的建议是值得欢迎的。 此处输入图片描述 图表
程序代码是： lockquote Graph.Java blockquote>
package Djikstra; import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner; 导入Djikstra.Vertex; public class Graph { Vertex [] vertexes; public Graph（String file）引发FileNotFoundException { Scanner sc = new Scanner（new File（file））; vertexes = new Vertex [sc.nextInt（）]; for（int v = 0; vDijkstra.java
package Djikstra; 导入Djikstra.Graph; import java.io.FileNotFoundException; import java.util.Comparator; import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.PriorityQueue; import java.util.Queue; import java.util.Set; 公共类Dijkstra { 图形图形;; public Dijkstra（String file）抛出FileNotFoundException { graph = new Graph（file）; } public void initialiseSingleSource（Graph G，int s）{//设置所有顶点到无限的最小距离和父对象的空值为 for（Vertex v：G.vertexes ）{ vd = 1000; v.p = null; } G.vertexes [s] .d = 0; //设置源的最小距离为0 $ b $ public void relax（Vertex u，Vertex v，int weight）{ if（v.d>（ud + weight ））{ vd = u.d + weight; v.p = u; public int weightFunc（图G，Vertex u，Vertex v）{//从顶点u获得边的权重v int重量= u.neighbours.get（v.id）; 回报重量; } public class VertexComparator实现比较器<顶点> {//由它们的d（与源的最小距离）键值的最小优先级队列值 @Override public int compare（Vertex v1，Vertex v2）{ return（v1.d-v2.d）; $ b public int indexForName（图G，字符串名）{//从顶点获取索引（int v = 0; v
输入文件dijkstraGraph.txt
7 A B C D E F G AB 5 AC 10 BE 3 BD 6 DF 6 EC 2 EG 2 ED 2 GF 2输出：
从源顶点打印所有顶点的最小距离A Id：距离：0 Id：G距离：10 Id：F距离：16 Id ：E距离：8 Id：C距离：10 Id：D距离：10 Id：B距离：5 解决方案
不是初始化队列 Q 与所有节点，只是初始化它与源节点。 pre $ for（Vertex v：G.vertexes）{//将源添加到优先级队列 Q.add（G.vertexes [S]）; }
然后当您遍历邻居时，将它们添加到 Q
for（String vertexId：u.neighbours.keySet（））{//查看的邻居//提取顶点 int vertexNum = indexForName（G，vertexId）; 顶点v = G.vertexes [vertexNum]; int w = weightFunc（G，u，v）; 放松（u，v，w）; Q.add（v）; $ / code>新输出：
从源顶点打印所有顶点的最小距离A Id：C距离：10 Id：距离：0 Id：F距离： 12 Id：G距离：10 Id：B距离：5 Id：E距离：8 Id：D距离：10
This is the implementation of Djikstra algorithm in java i have followed from book Introduction to Algorithms.But the results are not accurate in some cases.For the graph below,the output is showing the minimum distance of vertex F from source vertex A as 16,which actually is 12.I am fairly new in algorithm,so any suggestions in improvement in code is welcome. enter image description here Graph
The code of program is:
Graph.Java
package Djikstra; import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner; import Djikstra.Vertex; public class Graph { Vertex[] vertexes; public Graph(String file) throws FileNotFoundException{ Scanner sc = new Scanner(new File(file)); vertexes=new Vertex[sc.nextInt()]; for (int v = 0; v < vertexes.length; v++){ vertexes[v] = new Vertex(sc.next()); } while (sc.hasNext()) { int v1= indexForName(sc.next()); //read source vertex String destination=sc.next(); //read destination vertex int w=sc.nextInt(); //read weight of the edge vertexes[v1].neighbours.put(destination, w); //put the edge adjacent to source vertex } sc.close(); } public int indexForName(String name) { for (int v = 0; v < vertexes.length; v++) { if (vertexes[v].id.equals(name)) return v; } return -1; }
}
Dijkstra.java
package Djikstra; import Djikstra.Graph; import java.io.FileNotFoundException; import java.util.Comparator; import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.PriorityQueue; import java.util.Queue; import java.util.Set; public class Dijkstra { Graph graph;; public Dijkstra(String file) throws FileNotFoundException{ graph = new Graph(file); } public void initialiseSingleSource(Graph G,int s){ //set min distance of all vertex to infinite and parent to null for(Vertex v:G.vertexes){ v.d=1000; v.p=null; } G.vertexes[s].d=0; //set min distance of source to 0 } public void relax(Vertex u,Vertex v,int weight){ if(v.d>(u.d + weight)){ v.d=u.d+weight; v.p=u; } } public int weightFunc(Graph G,Vertex u,Vertex v){ //to get weight of an edge from vertex u to v int weight=u.neighbours.get(v.id); return weight; } public class VertexComparator implements Comparator<Vertex>{ //min priority queue keyed by their d(min distance from source) values @Override public int compare(Vertex v1, Vertex v2) { return (v1.d-v2.d); } } public int indexForName(Graph G,String name) { //to get index from the id of vertex for (int v = 0; v < G.vertexes.length; v++) { if (G.vertexes[v].id.equals(name)) return v; } return -1; } public Set<Vertex> dijkstraAlgo(Graph G,int s){ initialiseSingleSource(G,s); Set<Vertex> set=new HashSet<Vertex>(); //intitially empty set of vertexes Queue<Vertex> Q=new PriorityQueue<Vertex>(10,new VertexComparator()); //min priority queue for(Vertex v:G.vertexes) //add all vertexes to priority queue Q.add(v); while(Q.size()!=0){ Vertex u=Q.poll(); //extract vertex which have min distance in priority queue set.add(u); //add that vertex to set for(String vertexId:u.neighbours.keySet()){ //see neighbours of vertex extracted int vertexNum=indexForName(G,vertexId); //get index for neighbour vertex in vertexes array Vertex v=G.vertexes[vertexNum]; int w=weightFunc(G,u,v); //get weight of edge from Vertex u to v relax(u,v,w); } } return set; } public static void main(String[] args) throws FileNotFoundException{ String fileName = "C:/Users/Dell PC/Algorithm_Workspace/Graph_CLRS/src/Djikstra/dijkstraGraph.txt"; Dijkstra dijkstra=new Dijkstra(fileName); Set<Vertex> vertexInfo=dijkstra.dijkstraAlgo(dijkstra.graph, 0); System.out.println("Printing min distance of all vertexes from source vertex A "); for(Vertex v:vertexInfo){ System.out.println("Id: " + v.id + " distance: " + v.d); } } } class Vertex{ String id; int d; //to store min distance from source Vertex p; //to store last vertex from which min distance is reached Map<String,Integer> neighbours; //to store edges of adjacent to the vertex public Vertex(String id){ this.id=id; neighbours=new HashMap<String,Integer>(); }
}
The input file dijkstraGraph.txt
7 A B C D E F G A B 5 A C 10 B E 3 B D 6 D F 6 E C 2 E G 2 E D 2 G F 2
Output:
Printing min distance of all vertexes from source vertex A Id: A distance: 0 Id: G distance: 10 Id: F distance: 16 Id: E distance: 8 Id: C distance: 10 Id: D distance: 10 Id: B distance: 5
解决方案
Instead of initializing the queue Q with all nodes, just initialize it with the source node.
for (Vertex v : G.vertexes){ // add source to priority queue Q.add(G.vertexes[s]); }and then when you iterate over the neighbors, add them to Q
for (String vertexId : u.neighbours.keySet()) { // see neighbours of // vertex extracted int vertexNum = indexForName(G, vertexId); Vertex v = G.vertexes[vertexNum]; int w = weightFunc(G, u, v); relax(u, v, w); Q.add(v); }New output:
Printing min distance of all vertexes from source vertex A Id: C distance: 10 Id: A distance: 0 Id: F distance: 12 Id: G distance: 10 Id: B distance: 5 Id: E distance: 8 Id: D distance: 10
更多推荐
Dijkstra算法在Java中的实现
发布评论