Java中Dijkstra算法的实现

Question

Java中Dijkstra算法的实现

3

这是我从《算法导论》一书中学习并实现的Java版Djikstra算法。但在某些情况下，结果不准确。对于下面的图形，输出显示源顶点A到顶点F的最小距离为16，但实际上是12。我对算法还比较新手，因此欢迎任何改进代码的建议。图片描述图形

程序代码如下：

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

}

输入文件 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

输出：

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

- adi

1

你能否添加一个期望输出部分，以展示哪些内容是错误的？ - mech

@mech F点到A点的最小距离为12，如图所示。但输出结果显示为16。其他所有最小距离都是正确的。请参见上面的图像。 - adi

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- MartinS · Accepted Answer

不要对所有节点都初始化队列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