求图的最短路径并打印路由表

Question

这是针对java中的数据结构类，我需要创建一个图形来读取文本输入，将此信息转换为图形，然后从那里打印邻接列表并打印最大生成树，我已经完成了。然而，最后一个方面是

您的程序必须为网络中的每对 [i,j] (i != j) 计算机生成完整的路由表，即从 i 到 j 的最佳路由上的第一台计算机。如果 i 和 j 有直接连接，则 j 将是该路由（对 [i,j]）的结果（表条目）。如果从i到j的最佳路线是i->;一个-> b-> j，则 a 将是该路线的结果（表条目）。然后，我们可以通过查看 [i,j] (=a)、[a,j] (=b)、[b,j] (=j) 中的值来构建路线。

基本上就是 Dijksta 算法。但是，我无法使用任何处理图形的 Java API（所有其他 API 都是允许的）。到目前为止，我的

import java.util.ArrayList;
//import java.util.Stack;

public class Graph2 {

    ArrayList<Vertex> vert = new ArrayList<Vertex>();
    private static int counter = 0;
    private int edges;
    private Edge[] allEdges = new Edge[50];

    private class Vertex{
        String ip;
        private int id;
        ArrayList<Edge> nb = new ArrayList<Edge>();
        /**
         * Constructor for Vertex
         * @param String of IP
         */
        public Vertex(String s){
            ip = s;
            id = counter;
            counter++;
        }
        /**
         * Gets the ID of a vertex
         * @return unique ID
         */
        public int getId(){
            return id;
        }
        /*
        public boolean isSame(Vertex v){
            if(this.ip.equals(v.getIp()))
                return true;
            else
                return false;
        }
        */
        /**
         * Gets the IP of a vertex
         * @return the IP of the vertex
         */
        public String getIp(){
            return this.ip;
        }
        /**
         * Adds an edge to nb
         * @param edge to be added
         */
        public void addList(Edge e){
            nb.add(e);
        }
        /**
         * Determines if an edge exists
         * @param edge to be checked
         * @return true if exists, false if not
         */
        public boolean exists(Edge e){
            if(nb.indexOf(e) != -1){
                return true;
            }
            else
                return false;
        }
        /**
         * Gets the size of an edge
         * @return size of edge
         */
        public int edgeSize(){
            return nb.size();
        }
        /**
         * Gets the edges
         * @return String of edges
         */
        public String getEdges(){ 
            String all = "";
            Edge e;
            for(int i = 0; i < nb.size(); i++){
                e = nb.get(i);
                int ti = this.getId();
                int fin = e.getFinish().getId();
                if(ti == fin)
                    all += e.getStart().getId() + " ";
                else
                    all += e.getFinish().getId() + " ";
            }
            return all;
        }
        /**
         * Overrides toString method
         * @return ID and IP of vertex
         */
        public String toString(){
            return id + " " + " " + ip;
        }
    }

    private class Edge{

        int weight;
        Vertex finish;
        Vertex start;
        /**
         * Constructor of Edge
         * @param vertex 1, start vertex
         * @param vertex 2, endpoint vertex
         * @param weight of edge
         */
        public Edge(Vertex v, Vertex v2, int w){
            start = v;
            finish = v2;
            weight = w;
        }
        /**
         * Gets the start of an edge
         * @return edge start
         */
        public Vertex getStart(){
            return start;
        }
        /**
         * Gets the endpoint of an edge
         * @return endpoint of edge
         */
        public Vertex getFinish(){
            return finish;
        }
        /**
         * Gets the weight of an edge
         * @return weight of edge
         */
        public int getWeight(){
            return weight;
        }
        /**
         * Overrides toString
         * @return start of edge and endpoint of edge
         */
        public String toString(){
            return start + " " + finish;
        }
    }
    /**
     * Adds an edge to 2 verticies
     * @param s, starting vertex IP
     * @param t, enpoint vertex IP
     * @param w, weight of edge
     */
    public void add(String s, String t, int w){
        Vertex v3, v4;
        v3 = exists(new Vertex(s));
        v4 = exists(new Vertex(t));
        Edge e;
        if(v3 == null  && v4 == null){
            v3 = new Vertex(s);
            v4 = new Vertex(t);
            vert.add(v3);
            vert.add(v4);
            e = new Edge(v3, v4, w);
            v3.addList(e);
            v4.addList(e);
        }
        else if(v3 != null && v4 == null){
            counter--;
            v4 = new Vertex(t);
            vert.add(v4);
            e = new Edge(v3, v4, w);
            v3.addList(e);
            v4.addList(e);
        }
        else if(v3 == null && v4 !=null){
            counter--;
            v3 = new Vertex(s);
            vert.add(v3);
            e = new Edge(v3, v4, w);
            v3.addList(e);
            v4.addList(e);
        }
        else{
            counter -= 2;
            e = new Edge(v3, v4, w);
            if(!v3.exists(e)){
                v3.addList(e);
                v4.addList(e);
            }
        }
        allEdges[edges] = e;
        edges++;
    }
    /**
     * Determines if an edge already exists
     * @param vertex to be checked
     * @return vertex if exists, null if not
     */
    public Vertex exists(Vertex v){
        for(int i = 0; i < vert.size(); i++){
            if(v.getIp().equals(vert.get(i).getIp()))
                return vert.get(i);
        }
        counter--;
        return null;
    }
    /**
     * Puts vert ArrayList into an array
     * @return String array of vert
     */
    public String[] toArray(){
        String[] all = new String[vert.size()];
        for(int i = 0; i < vert.size(); i++){
            all[i] = vert.get(i).toString();
        }
        return all;
    }
    /**
     * Determines if a vertex is adjacent to another vertex
     * @return String array of adjacent verticies
     */
    public String[] adjaceny(){
        String[] all = new String[vert.size()];
        Vertex v1;
        for(int i = 0; i < vert.size(); i++){
            v1 = vert.get(i);
            all[i] = v1.getEdges();
        }
        return all;
    }
    /**
     * Determines which vertex is in which cluster
     * @return String array of clusters
     */

    /*
    public String[] cluster(){
        Vertex[] temp = (Vertex[]) vert.toArray();
        Sorter sort = new Sorter();

        sort.heapsort(temp);
        String[] cluster = new String[vert.size()];
        int[] verts = new int[vert.size()];
        for(int i = 0; i < vert.size();i++)
            verts[i] = i; 
        return null;

    }
    */
    /**
     * Gets the max spanning tree of the graph
     * @return spanning tree of graph
     */
    public String[] maxTree(){
        sortEdges();
        String[] max = new String[vert.size() -1];
        Edge e;
        for(int i = 0; i < vert.size()-1; i++){
            e = allEdges[i];
            max[i] = e.getStart().getId() + ", " + e.getFinish().getId() + ", " + e.getWeight();
        }
        return max;
    }
    /**
     * Sorts edges by max weight
     */
    private void sortEdges(){
        Sorter sort = new Sorter();
        sort.heapsort(allEdges);
    }

    public class Sorter{
        /**
         * Heapsorts the Object array
         * @param Object array to be sorted
         */
        public void heapsort(Object[] a)
        {
            for(int i = edges / 2; i >= 0; i-- )  /* buildHeap */
                percDown(a, i, edges);
            for( int i = edges - 1; i > 0; i-- )
            {
                swapReferences( a, 0, i );            /* deleteMax */
                percDown( a, 0, i );
            }
        }
        /**
         * Performs swapping of elements
         * @param Object array
         * @param index1
         * @param index2
         */
        public void swapReferences(Object[] a, int index1, int index2 )
        {
            if(a[0] instanceof Edge){
                Edge tmp = (Edge)a[index1];
                a[index1] = a[index2];
                a[index2] = tmp;
            }
            else if(a[0] instanceof Vertex){
                Vertex temp = (Vertex)a[index1];
                a[index1] = a[index2];
                a[index2] = temp;
            }
        }


        /**
         * Internal method for heapsort.
         * @param i the index of an item in the heap.
         * @return the index of the left child.
         */
        private int leftChild(int i)
        {
            return 2 * i + 1;
        }

        /**
         * Internal method for heapsort that is used in
         * deleteMax and buildHeap.
         * @param a an array of Comparable items.
         * @int i the position from which to percolate down.
         * @int n the logical size of the binary heap.
         */
        private void percDown(Object[] a, int i, int n)
        {
            int child;
            if(a[0] instanceof Edge){
                Edge tmp;
                for( tmp = (Edge) a[i]; leftChild(i) < n; i = child )
                {
                    child = leftChild(i);
                    if( child != n - 1 && ((Edge)a[child]).getWeight() - ((Edge)(a[child + 1])).getWeight() > 0 )
                        child++;
                    if(tmp.getWeight() - ((Edge)a[child]).getWeight() > 0 )
                        a[i] = a[child];
                    else
                        break;
                }   
                a[i] = tmp;
            }
            else if(a[0] instanceof Vertex){
                Vertex temp;
                for(temp = (Vertex) a[i]; leftChild(i) < n; i = child){
                    child = leftChild(i);
                    if(child != n-1 && ((Vertex)a[child]).edgeSize() - ((Vertex)a[child+1]).edgeSize() > 0)
                        child++;
                    if(temp.edgeSize() - ((Vertex)a[child]).edgeSize() > 0)
                        a[i] = a[child];
                    else
                        break;
                }
                a[i] = temp;
            }
        }
    }
        }
}

主要内容包括：

import java.util.*;
import java.io.*;

public class pg6main {

    public static void main(String[] args) throws IOException{

        String filename;
        String first, second;
        int weight;
        Graph2 graph = new Graph2();
        Scanner kb = new Scanner(System.in);
        boolean go = false;
        Scanner infile = null;
        PrintWriter outfile = new PrintWriter(new FileWriter("results.txt"));
        do{
            try{
                System.out.print("Enter a file to read from: ");
                filename = kb.nextLine();
                infile = new Scanner(new FileReader(filename));
            }catch(Exception e){
                go = true;
                System.out.println("file doesn't exist");
            }
        }while(go);

        while(infile.hasNext()){
            first = infile.next().trim();
            second = infile.next().trim();
            weight = Integer.parseInt(infile.nextLine().trim());
            graph.add(first, second, weight);
        }
        outfile.println("IP and their unique IDs: ");

        String[] a = graph.toArray();
        for(int i = 0; i < a.length; i++)
            outfile.println(a[i]);

        outfile.println("Adjaceny List: ");

        String[] adj = graph.adjaceny();
        for(int j = 0; j < adj.length; j++)
            outfile.println(j + ": " + adj[j]);

        outfile.println("Max spanning tree: ");

        String[] max = graph.maxTree();
        for(int k = 0; k < max.length; k++)
            outfile.println("(" + max[k] + ") ");
        /*
        //Attempting to do clusters based on length of string of neighbors, does not work
        for(int x = 0; x < adj.length; x++){
            if(adj[x].length() > adj[x+1].length()){
                outfile.println("WHAT I DID: " + adj[x]);
            }
            else if(adj[x].length() == adj[x+1].length()){
                adj[x] = adj[x+1];
                outfile.println("WHAT I DID: " + adj[x]);
            }
            else if(adj[x].length() < adj[x+1].length()){
                adj[x] = adj[x+1];
                outfile.println("WHAT I DID: " + adj[x]);
        }
        */

        /*//Attempted to do neighbors slighly different way
        String[] cluster = graph.cluster();
        for(int x = 0; x < cluster.length; x++){
            if(cluster[x] != null)
                outfile.println(cluster[x]);
        */  


    outfile.close();
    }//end main

}//end pg6main

我想知道是否有人可以提供帮助，直到今天我才使用过图表。到目前为止，我相信我的代码按预期工作，但我的逻辑可能存在一些错误。基本上我的问题是 Dijkstra 的大多数实现都有参数作为图表，我不确定这是否真的是我应该这样做的方式。感谢您的任何帮助。

Answer 1

您应该使用 Floyd 算法，它会为您提供完整的最短路线表，与您完全一样要求中描述。

正如您从伪代码中看到的，它非常简单，您所需要做的就是创建一个二维数组并用边对其进行初始化。 （所以基本上这是你的加权邻接表。）