java - 图上的 Floyd Warshall 算法
问题描述
我试图使用类的 floyd warshall 算法找到到图的所有节点的最短路径。我得到了图表的基本代码,并尝试通过伪代码实现算法,但还没有弄清楚如何根据迭代来选择特定的边。
这是算法的代码。我试图改变的部分是“用邻接矩阵权重值初始化”我不知道如何选择那个特定的边权重。
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;
}
}
解决方案
您可以将所有单元格初始化为无穷大,然后对于从顶点 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());
}
推荐阅读
- asp.net-core - 从 InMemory 数据库中删除数据时,内存使用量不会减少
- javascript - 通过 jQuery 创建新的 DOM 元素时,为什么要添加空的 Style 属性?
- mongodb - 从对象数组中删除特定的嵌套对象
- azure - USQL 中的 DateTime 自动转换为 parquet 文件中的 Unix Timestamp
- maven - 如何在 pom.xml 中正确排除 springboot-actuator
- javascript - 更改所有出现的字符 javascript/reactjs 的颜色
- sql - 根据具有不同过滤选项的同一列上的 where 条件从表中选择详细信息
- ios - 目前UITableViewController 的门格TableViewController?
- php - boostrap 文本框只显示一行
- node.js - 如何部署包含分叉 github 存储库的 heroku 应用程序