gpt4 book ai didi

java - Java中Dijkstra算法的实现

转载 作者:塔克拉玛干 更新时间:2023-11-02 08:06:45 24 4
gpt4 key购买 nike

这是 Djikstra 算法在 java 中的实现,我从算法介绍一书中遵循。但在某些情况下结果不准确。对于下图,输出显示顶点 F 与源顶点 A 的最小距离作为 16,实际上是 12。我在算法方面相当新,所以欢迎任何改进代码的建议。 enter image description here

程序代码为:

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

最佳答案

不是用所有节点初始化队列Q,而是用源节点初始化它。

    for (Vertex v : G.vertexes){ // add source to priority queue
Q.add(G.vertexes[s]);
}

然后当您遍历邻居时,将它们添加到 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);
}

新输出:

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

关于java - Java中Dijkstra算法的实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35546147/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com