我一直在研究这段代码，我需要创建一个动态完整图，并尝试通过访问每个顶点一次来找到从开始顶点到结束的最短路径。经过一番研究，我找到了哈密顿循环问题的代码并将其添加到我的代码中。运行这段代码后，我得到了这个：
run:
6
18.0
19.0
16.0
18.0
13.0
20.0
13.0
15.0
12.0
18.0
18.0
12.0
Exception in thread "AWT-EventQueue-0" java.lang.NullPointerException
15.0
15.0
12.0
Shortest path from START to END:
15
15
at org.jgrapht.graph.AbstractBaseGraph.getEdgeWeight(AbstractBaseGraph.java:470)
at org.jgrapht.graph.GraphDelegator.getEdgeWeight(GraphDelegator.java:292)
at demoweightedgraph.DemoWeightedGraph.hamiltonianCycle(DemoWeightedGraph.java:147)
at demoweightedgraph.DemoWeightedGraph.buildGraph(DemoWeightedGraph.java:98)
at demoweightedgraph.DemoWeightedGraph.createAndShowGui(DemoWeightedGraph.java:45)
at demoweightedgraph.DemoWeightedGraph.access$000(DemoWeightedGraph.java:34)
at demoweightedgraph.DemoWeightedGraph$1.run(DemoWeightedGraph.java:69)
at java.awt.event.InvocationEvent.dispatch(InvocationEvent.java:311)
at java.awt.EventQueue.dispatchEventImpl(EventQueue.java:756)
at java.awt.EventQueue.access$500(EventQueue.java:97)
at java.awt.EventQueue$3.run(EventQueue.java:709)
at java.awt.EventQueue$3.run(EventQueue.java:703)
at java.security.AccessController.doPrivileged(Native Method)
at java.security.ProtectionDomain$JavaSecurityAccessImpl.doIntersectionPrivilege(ProtectionDomain.java:80)
at java.awt.EventQueue.dispatchEvent(EventQueue.java:726)
at java.awt.EventDispatchThread.pumpOneEventForFilters(EventDispatchThread.java:201)
at java.awt.EventDispatchThread.pumpEventsForFilter(EventDispatchThread.java:116)
at java.awt.EventDispatchThread.pumpEventsForHierarchy(EventDispatchThread.java:105)
at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:101)
at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:93)
at java.awt.EventDispatchThread.run(EventDispatchThread.java:82)
BUILD SUCCESSFUL (total time: 1 second)
请注意，第一行打印生成的随机数，之后我打印边缘的权重以进行检查，最后在“从开始到结束的最短路径”之后打印 (vertices.size() * (vertices.size() - 1) / 2) 和 g.edgeSet().size() 检查图形是否完整。
这是我的代码：
public class DemoWeightedGraph {
private static void createAndShowGui() {
JFrame frame = new JFrame("DemoGraph");
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.setSize(200,200);
int i = generateNumberByRange(4,6);
System.out.println(i);
ListenableGraph<String, MyEdge> g = buildGraph(i);
mxGraphAnalysis mga = mxGraphAnalysis.getInstance();
JGraphXAdapter<String, MyEdge> graphAdapter =
new JGraphXAdapter<String, MyEdge>(g);
mxIGraphLayout layout = new mxCircleLayout(graphAdapter);
layout.execute(graphAdapter.getDefaultParent());
frame.add(new mxGraphComponent(graphAdapter));
frame.pack();
//frame.setLocationByPlatform(true);
frame.setVisible(true);
}
public static void main(String[] args) {
SwingUtilities.invokeLater(new Runnable() {
public void run() {
createAndShowGui();
}
});
}
public static class MyEdge extends DefaultWeightedEdge {
@Override
public String toString() {
return String.valueOf(getWeight());
}
}
public static ListenableGraph<String, MyEdge> buildGraph(int in) {
ListenableDirectedWeightedGraph<String, MyEdge> graph =
new ListenableDirectedWeightedGraph<String, MyEdge>(MyEdge.class);
for(int j=0;j<in;j++){
graph.addVertex(String.valueOf(j));
}
for (int i = 0; i < in; i++) {
for (int j = i + 1; j < in; j++) {
MyEdge e1 = graph.addEdge(String.valueOf(i),String.valueOf(j));
graph.setEdgeWeight(e1, generateNumberByRange(10,20));
System.out.println(graph.getEdgeWeight(e1));
}
}
System.out.println("Shortest path from START to END:");
List sp = hamiltonianCycle(graph);
// List shortest_path = DijkstraShortestPath.findPathBetween(graph,"1",String.valueOf(i));
// for(int k=0; k< shortest_path.size(); k++){
// shortest_path.get(k);
// }
System.out.println(sp);
return graph;
}
public static int generateNumberByRange(int START, int END){
return ThreadLocalRandom.current().nextInt(START, END + 1);
}
protected mxFibonacciHeap createPriorityQueue()
{
return new mxFibonacciHeap();
}
public static <V, E> List<V> hamiltonianCycle(ListenableDirectedWeightedGraph<V, E> g)
{
List<V> vertices = new LinkedList<>(g.vertexSet());
System.out.println((vertices.size() * (vertices.size() - 1) / 2));
System.out.println(g.edgeSet().size());
// If the graph is not complete then return null since this algorithm
// requires the graph be complete
if ((vertices.size() * (vertices.size() - 1) / 2) != g.edgeSet().size()) {
return null;
}
List<V> tour = new LinkedList<>();
// Each iteration a new vertex will be added to the tour until all
// vertices have been added
while (tour.size() != g.vertexSet().size()) {
boolean firstEdge = true;
double minEdgeValue = 0;
int minVertexFound = 0;
int vertexConnectedTo = 0;
// A check will be made for the shortest edge to a vertex not within
// the tour and that new vertex will be added to the vertex
for (int i = 0; i < tour.size(); i++) {
V v = tour.get(i);
for (int j = 0; j < vertices.size(); j++) {
double weight = g.getEdgeWeight(g.getEdge(v, vertices.get(j)));
if (firstEdge || (weight < minEdgeValue)) {
firstEdge = false;
minEdgeValue = weight;
minVertexFound = j;
vertexConnectedTo = i;
}
}
}
tour.add(vertexConnectedTo, vertices.get(minVertexFound));
vertices.remove(minVertexFound);
}
return tour;
}
}
编辑：我对这段代码的唯一问题是 hamiltoniancycle 方法中的 getedgeweight 方法