java - 图上的 Floyd Warshall 算法

Question

我尝试使用类的弗洛伊德·沃歇尔算法找到到图所有节点的最短路径。我获得了该图的基本代码，并尝试通过伪代码实现该算法，但还没有弄清楚如何根据迭代来选择特定的边。

这是该算法的代码。我试图改变的部分是“用邻接矩阵权重值初始化”我不确定如何选择特定的边权重。

public static void FloydWarshall(Graph g) {
        int V = g.getvCount();

        // to store the calculated distances
        float dist[][] = new float[V][V];

        // initialize with adjacency matrix weight values
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                for(int k = 0; k<=g.edgeList.size(); k++){
                    if(g.edgeList.get(i).head.equals(i) && g.edgeList.get(j).tail.equals(j)){
                        int label = Integer.parseInt(g.edgeList.get(k).label);
                dist[i][j] = label;
                }}
            }
        }

        // loop through all vertices one by one
        for (int k = 0; k < V; k++) {
            // pick all as source
            for (int i = 0; i < V; i++) {
                // pick all as destination
                for (int j = 0; j < V; j++) {
                    // If k is on the shortest path from i to j
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        // update the value of dist[i][j]
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

        // shortest path matrix
        for (int z = 0; z < V; z++) {
            for (int j = 0; j < V; j++) {
                // if value is infinity
                if (dist[z][j] == Float.MAX_VALUE)
                    System.out.print("INF ");
                else
                    System.out.print(dist[z][j] + "   ");
            }
            System.out.println();
        }

这是边缘的代码

public class Edge implements Comparable<Edge> {

    String label;
    Node tail;
    Node head;

    public Edge(Node tailNode, Node headNode, String theLabel) {
        setLabel(theLabel);
        setTail(tailNode);
        setHead(headNode);
    }

    public String getLabel() {
        return label;
    }

    public Node getTail() {
        return tail;
    }

    public Node getHead() {
        return head;
    }

    public void setLabel(String s) {
        label = s;
    }

    public void setTail(Node n) {
        tail = n;
    }

    public void setHead(Node n) {
        head = n;
    }

    @Override
    public int compareTo(Edge edge) {
        try {
            int edge1 = Integer.parseInt(edge.label);
            int edge2 = Integer.parseInt(edge.label);
            return Integer.compare(edge1, edge2);
        } catch (NumberFormatException e) {
            System.out.println(e);
        }
        return 0;
    }
}

此外，这是我拥有的图形类的代码。

import java.util.*;

public class Graph {

    ArrayList<Node> nodeList;
    ArrayList<Edge> edgeList;

    public Graph() {
        nodeList = new ArrayList<Node>();
        edgeList = new ArrayList<Edge>();
    }

    public ArrayList<Node> getNodeList() {
        return nodeList;
    }

    public ArrayList<Edge> getEdgeList() {
        return edgeList;
    }

    public void addNode(Node n) {
        nodeList.add(n);
    }

    public void addEdge(Edge e) {
        edgeList.add(e);
    }

    public String toString() {
        String s = "Graph g.\n";
        if (nodeList.size() > 0) {
            for (Node n : nodeList) {
                // Print node info
                String t = "\nNode " + n.getName() + ", abbrev " + n.getAbbrev() + ", value " + n.getVal() + "\n";
                s = s.concat(t);
            }
            s = s.concat("\n");
        }

        return s;
    }

    public void sortNodes(){
        Collections.sort(nodeList);
    }

    private int vCount;
    private float[][] adj;

    public int getvCount() {
        return vCount;
    }

    public float[][] getAdj() {
        return adj;
    }

    public Graph(int vCount) {
        this.vCount = vCount;
        adj = new float[vCount][vCount];
        for (int i = 0; i < vCount; i++) {
            for (int j = 0; j < vCount; j++) {
                if (i != j) {
                    adj[i][j] = Float.MAX_VALUE;
                }

            }
        }
    }

    public void addEdge(int i, int j, float weight) {
        adj[i][j] = weight;
    }

    public void removeEdge(int i, int j) {
        adj[i][j] = Float.MAX_VALUE;
    }

    public boolean hasEdge(int i, int j) {
        if (adj[i][j] != Float.MAX_VALUE && adj[i][j] != 0) {
            return true;
        }
        return false;
    }

    public List<Integer> neighbours(int vertex) {
        List<Integer> edges = new ArrayList<Integer>();
        for (int i = 0; i < vCount; i++)
            if (hasEdge(vertex, i))
                edges.add(i);
        return edges;
    }




}

Answer 1

可以将所有单元初始化为无穷大，然后对于每个从顶点 i 到顶点 j 存在边的单元 [i][j]，将其距离设置为边权重。您可以通过随后迭代所有边来完成此操作。

 // initialize with adjacency matrix weight values
 // set all to be initially infinity
 for (int i = 0; i < V; i++) {
     for (int j = 0; j < V; j++) {
          dist[i][j] = Float.MAX_VALUE;
     }
 }
 // set all edge weights
 for(int k = 0; k <= g.edgeList.size(); k++){
      Edge e = g.edgeList.get(k);
      int i = Integer.parseInt(e.getHead().label);
      int j = Integer.parseInt(e.getTail().label);
      dist[i][j] = Integer.parseInt(e.getLabel());
 }