0

Im attempting to find the shortest path to all the nodes of a graph using the floyd warshall algorithm for a class. I was given the base code for the graph, and have tried implementing the algorithm through pseudocode, but havent figured out how to pick the specific edge based on the iteration im in.

Here is the code for the algorithm. the part that im trying to change is "initialize with adjacency matrix weight values" im not sure how to select that specific edge weight.

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

And here is the code for the edge

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

Additionally here is the code for the graph class that i have.

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




}

1 Answer 1

0

You can initialize all cells to be infinity, and then for each cell [i][j] where there is an edge from vertex i to vertex j, set its distance to be the edge weight. You could do this by iterating through all edges afterwards.

 // 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());
 }
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.