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