Dijkstra算法在Java中的实现 [英] Implementation of Dijkstra Algorithm In 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; v  vertexes [v] = new Vertex（sc.next（））; 
} 
 
 while（sc.hasNext（））{
 int v1 = indexForName（sc.next（））; //读取源顶点
 String destination = sc.next（）; //读取目标顶点
 
 int w = sc.nextInt（）; //读取边的权重
 
 
 vertexes [v1] .neighbours.put（destination，w）; //将边缘放在源顶点附近
} 
 sc.close（）; 
 
 $ b $ public int indexForName（String name）{
 for（int v = 0; v< vertexes.length; v ++）{
 if（vertexes [ v] .id.equals（name））
 return v; 
} 
返回-1; 
} 
  

}

Dijkstra.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  if（G.vertexes [v] .id.equals（name））
 return v; 
} 
返回-1; 
} 
 
 public Set< Vertex> dijkstraAlgo（Graph G，int s）{
 initialiseSingleSource（G，s）; 
 Set< Vertex> set = new HashSet< Vertex>（）; //初始顶点集合
 
 Queue< Vertex> Q =新的PriorityQueue< Vertex>（10，新的VertexComparator（））; //最小优先级队列
 
（顶点v：G.vertexes）//将所有顶点添加到优先级队列
 Q.add（v）; 
 
 while（Q.size（）！= 0）{
 Vertex u = Q.poll（）; //提取在优先队列中有最小距离的顶点
 set.add（u）; //添加该顶点来设置
 for（String vertexId：u.neighbours.keySet（））{//查看提取的顶点的邻居
 int vertexNum = indexForName（G，vertexId）; //得到顶点数组中的邻居顶点索引
顶点v = G.vertexes [vertexNum]; 
 int w = weightFunc（G，u，v）; //得到Vertex u到v 
的边的权重relax（u，v，w）; 
} 
} 
 
返回集; 
 
 
 
 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（从源顶点A打印所有顶点的最小距离）; （顶点v：vertexInfo）{
 System.out.println（Id：+ v.id +distance：+ v.d）; 
 
} 
} 
} 
 
类顶点{
字符串ID; 
 int d; //存储距离源的最小距离
顶点p; //存储最小距离的最后一个顶点
 Map< String，Integer>邻居; //存储与顶点相邻的边缘
 
 public Vertex（String id）{
 this.id = id; 
 neighbors = new HashMap< String，Integer>（）; 
} 
  

}

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

$ b

输出：

 从源顶点打印所有顶点的最小距离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中的实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！