尝试使用修改后的Dijkstra算法在Java中寻找图的最小宽路径权重。

huangapple 未分类评论57阅读模式
英文:

Trying to find smallest weight of widest path of a graph using modified Dijkstra's Algorithm in Java

问题

我需要从一个选定的节点到另一个节点在一个自动生成的图中找到最宽的路径。之后,我需要找到所计算路径上的“瓶颈”,即最小权重。目前,我不知道从哪里开始找到瓶颈,并且在展示路径方面遇到了困难。在Graph类中的printPath方法中,我目前遇到了堆栈溢出错误,这可能是由于无限递归造成的,尽管我不理解为什么会首先出现无限递归。我从这里使用了一些代码:https://www.geeksforgeeks.org/printing-paths-dijkstras-shortest-path-algorithm/,稍微修改了一下,以找到最大的路径,而不是最短的路径,同时还重命名了变量。我认为修改中的错误很可能是问题的一个来源。以下是我最近一次测试的输出:

输入一个正整数。
5
节点列表:{1,2,3,4,5}
边列表:{(2,3,17),(2,4,8),(3,5,3)}
输入一个起始节点。
1
输入一个目标节点。
5
顶点:1 --> 5
距离:20
路径:Exception in thread "main" java.lang.StackOverflowError
	at Graph.printPath(Graph.java:104)
	at Graph.printPath(Graph.java:104)
	at Graph.printPath(Graph.java:104)

以下是我的代码。我已经将代码放在了不同的类中,所以如果在合并到一个文件中时出现了错误,我向您道歉。我还为庞大且混乱的代码块道歉,但我认为在发布之前没有什么可以去除的内容。

(注:由于您要求只返回翻译好的部分,我只提供了代码的翻译部分,不包含额外的说明或解释。)

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Random;

public class Graph {
    // ...(其他部分的代码)

    public void printPath(int dest) {
        if (nodes.get(dest).getParent() == -1) {
            return;
        }
        printPath(nodes.get(dest).getParent()); // 此处发生堆栈溢出
        System.out.print((dest + 1) + " ");
    }
}

public class Node {
    // ...(其他部分的代码)
}

public class Edge {
    // ...(其他部分的代码)
}

public class Driver {
    public static void main(String[] args) {
        // ...(其他部分的代码)
    }
}

请注意,上述只是代码的翻译部分,如果您需要进一步的解释或修改,请随时提问。

英文:

I need to give the widest path from one chosen node to another in a self-generated graph. After this, I need to state the "bottleneck" or smallest weight on the computed path. As it is, I don't know where to start to find the bottleneck and I'm having trouble showing the path. Under the Graph class, in the printPath method, I am currently getting a StackOverflow Error from presumably infinite recursion, though I don't understand how its recurring infinitely in the first place. I've used some code from here: https://www.geeksforgeeks.org/printing-paths-dijkstras-shortest-path-algorithm/ with slight modification to find the largest path rather than the shortest as well renaming variables. I feel an error in said modification is most likely one source of the problem. Following is the output of my most recent test:

Enter a positive integer.
5
Node list: {1,2,3,4,5}
Edge list: {(2,3,17),(2,4,8),(3,5,3)}
Enter a source node.
1
Enter a destination node
5
Vertex: 1 --> 5
Distance: 20
Path: Exception in thread "main" java.lang.StackOverflowError
	at Graph.printPath(Graph.java:104)
	at Graph.printPath(Graph.java:104)
	at Graph.printPath(Graph.java:104)

Here's my code so far. I've had my code in separate classes, so I apologize for any errors I may have made combining them to one file. I also apologize for the massive and messy block of code but I don't think there's anything here I can weed out before posting.

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Random;

public class Graph{
	
	private ArrayList<Node> nodes = new ArrayList<Node>();
	private ArrayList<Edge> edges = new ArrayList<Edge>();
	private int[][] adjMatrix; 
	
	Graph(int numNodes, int weightBound, double probability){
		ArrayList<Node> tempNodeList = new ArrayList<Node>(numNodes);
		for(int i = 0; i < numNodes; i++) {
			Node tempNode = new Node(i+1);
			tempNodeList.add(tempNode);
		}
		this.nodes = tempNodeList;
		Random rand = new Random();
		for(int i = 0; i < numNodes; i++) {
			for(int j = i+1; j < numNodes; j++) {
				if(rand.nextInt((int)Math.round(1/probability)) == 0) {
					Edge tempEdge = new Edge(rand.nextInt(5*numNodes-1)+1, nodes.get(i), nodes.get(j));
					edges.add(tempEdge);
				}
			}
		}
		
		adjMatrix = new int[numNodes][numNodes];
		for(int i = 0; i < edges.size(); i++) {
			adjMatrix[edges.get(i).getNode(0).getID()-1][edges.get(i).getNode(1).getID()-1] = edges.get(i).getWeight();
			adjMatrix[edges.get(i).getNode(1).getID()-1][edges.get(i).getNode(0).getID()-1] = edges.get(i).getWeight();
		}
		
	}
	
	public void printGraph() {
		System.out.print("Node list: {");
		for(int i = 0; i < nodes.size(); i++) {
			nodes.get(i).printNode();
			if(i != nodes.size()-1) {
				System.out.print(",");
			}
		}
		System.out.println("}");
		System.out.print("Edge list: {");
		for(int i = 0; i < edges.size(); i++) {
			edges.get(i).printEdge();
			if(i != edges.size()-1) {
				System.out.print(",");
			}
		}
		System.out.println("}");
	}
	
	public void widestPath(int source, int dest){
		
		int numVertices = adjMatrix[0].length;
		int[] longestDists = new int[numVertices];
		boolean[] inPath = new boolean[numVertices];
		for(int i = 0; i < numVertices; i++) {
			inPath[i] = false;
		}
		longestDists[source] = 0;
		Node tempNode = nodes.get(source);
		tempNode.setParent(-1);
		nodes.set(source, tempNode);
		for(int i = 1; i < numVertices; i++) {
			int furthestNode = -1;
			int longestDist = Integer.MIN_VALUE;
			for(int index = 0; index < numVertices; index++) {
				if(!inPath[index] && longestDists[index] > longestDist) {
					furthestNode = index;
					longestDist = longestDists[index];
				}
			}
			
			inPath[furthestNode] = true;
			for(int index = 0; index < numVertices; index++) {
				int edgeWeight = adjMatrix[furthestNode][index];
				if(edgeWeight > 0 && ((longestDist + edgeWeight) > (longestDists[index]))){
					tempNode = nodes.get(index);
					tempNode.setParent(furthestNode);
					nodes.set(index, tempNode);
					longestDists[index] = longestDist + edgeWeight;
				}
			}
		}
		
		
		printResult(source, longestDists, dest);
		
	}
	
	public void printResult(int source, int[] dists, int dest) {
		System.out.println("Vertex: " + (source+1) + " --> " + (dest+1));
		System.out.println("Distance: " + dists[dest]);
		System.out.print("Path: ");
		printPath(dest);
	}
	
	public void printPath(int dest) {
		if(nodes.get(dest).getParent() == -1) {
			return;
		}
		printPath(nodes.get(dest).getParent()); // StackOverflow here
		System.out.print((dest+1) + " ");
	}
	

	
}


public class Node {

	private int ID;
	private int distance = Integer.MIN_VALUE;
	private int parent;

	
	Node(int id){
		this.ID = id;
	}
	
	public int getID() {
		return this.ID;
	}
	
	public void printNode() {
		System.out.print(this.ID);
	}
	
	public void setDist(int dist) {
		this.distance = dist;
	}
	
	public int getDist() {
		return this.distance;
	}
	
	public void setParent(int p) {
		this.parent = p;
	}
	
	public int getParent() {
		return this.parent;
	}
	
	

	
}


public class Edge {
	
	private int weight;
	private ArrayList<Node> vertices = new ArrayList<Node>(2);
	
	Edge(int weight){
		this.weight = weight;
	}
	
	Edge(int weight, Node n1, Node n2){
		this.weight = weight;
		this.vertices.add(n1);
		this.vertices.add(n2);
	}
	
	public int getWeight() {
		return weight;
	}
	
	public void setNodes(Node n1, Node n2) {
		this.vertices.set(0, n1);
		this.vertices.set(1, n2);
	}
	
	public ArrayList<Node> getNodes(){
		return vertices;
	}
	
	public void printEdge() {
		System.out.print("(" + vertices.get(0).getID() + "," + vertices.get(1).getID() + "," + this.weight + ")");
	}
	
	public int otherNodeIndex(int ID) {
		if(vertices.get(0).getID() == ID) {
			return 1;
		}else if(vertices.get(1).getID() == ID) {
			return 0;
		} else {
			return -1;
		}
	}
	
	public Node getNode(int index) {
		return vertices.get(index);
	}
	

}

public class Driver {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int input = -1;
		while(input <= 0) {
			System.out.println("Enter a positive integer.");
			input = sc.nextInt();
		}
		
		double probability = 0.25;
		Graph gr = new Graph(input, input*5, probability);
		
		gr.printGraph();
		int source = -1;
		int dest = -1;
		while(source < 0 || source > input) {
			System.out.println("Enter a source node.");
			source = sc.nextInt()-1;
		}
		while(dest < 0 || dest > input) {
			System.out.println("Enter a destination node");
			dest = sc.nextInt()-1;
		}
		
		gr.widestPath(source, dest);

	}

}

huangapple
  • 本文由 发表于 2020年5月4日 08:39:11
  • 转载请务必保留本文链接:https://java.coder-hub.com/61583487.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定