java - dijkstra算法的绘图图

Question

我已经实现了 Dijkstra 算法，但我还想为它实现一个 GUI。所以我有几个问题要问你们。

public class Dijkstra {

public static void main(String args[]) {

    Vertex v0 = new Vertex("A");
    Vertex v1 = new Vertex("B");
    Vertex v2 = new Vertex("C");
    Vertex v3 = new Vertex("D");
    Vertex v4 = new Vertex("E");
    Vertex v5 = new Vertex("F");
    Vertex v6 = new Vertex("G");
    Vertex v7 = new Vertex("H");

    v0.adjacencies = new Edge[]{new Edge(v1, 9), new Edge(v2, 1), new Edge(v6, 9), new Edge(v3, 2)};
    v1.adjacencies = new Edge[]{new Edge(v0, 9), new Edge(v4, 4)};
    v2.adjacencies = new Edge[]{new Edge(v0, 1), new Edge(v4, 2), new Edge(v5, 5)};
    v3.adjacencies = new Edge[]{new Edge(v0, 2), new Edge(v6, 5), new Edge(v7, 1)};
    v4.adjacencies = new Edge[]{new Edge(v1, 4), new Edge(v2, 2), new Edge(v5, 1)};
    v5.adjacencies = new Edge[]{new Edge(v4, 1), new Edge(v2, 5), new Edge(v6, 1), new Edge(v7, 4)};
    v6.adjacencies = new Edge[]{new Edge(v0, 9), new Edge(v5, 1), new Edge(v3, 5), new Edge(v7, 2)};
    v7.adjacencies = new Edge[]{new Edge(v5, 4), new Edge(v6, 2), new Edge(v3, 1)};

    Vertex[] vertices = {v0, v1, v2, v3, v4, v5, v6, v7};

    computePaths(v0);

    for (Vertex v : vertices) {
        System.out.println("Distance to " + v + ": " + v.getMinDistance());
        List<Vertex> path = getShortestPathTo(v);
        System.out.println("Path: " + path);
    }

}

public static void computePaths(Vertex source) {
    source.setMinDistance(0);

    PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
    vertexQueue.add(source);

    while (!vertexQueue.isEmpty()) {
        Vertex u = vertexQueue.poll();

        for (Edge e : u.adjacencies) {
            Vertex v = e.target;
            int weight = e.weight;
            int distanceThroughU = u.getMinDistance() + weight;

            if (distanceThroughU < v.getMinDistance()) {
                vertexQueue.remove(v);
                v.setMinDistance(distanceThroughU);
                v.previous = u;
                vertexQueue.add(v);
            }
        }
    }
}

public static List<Vertex> getShortestPathTo(Vertex target) {
    List<Vertex> path = new ArrayList<Vertex>();

    for (Vertex vertex = target; vertex != null; vertex = vertex.previous) {
        path.add(vertex);
    }

    Collections.reverse(path);
    return path;
}

这是实现的样子(没有 GUI)。我看到有一个名为 JUNG 的图形库，我下载了它。我试图通过将以下代码添加到我的主要方法来绘制我的图形。

SimpleGraphDraw f = new SimpleGraphDraw();

    DirectedSparseGraph g = new DirectedSparseGraph();
    g.addVertex(v0);
    g.addVertex(v1);
    g.addVertex(v2);
    g.addVertex(v3);
    g.addVertex(v4);
    g.addVertex(v5);
    g.addVertex(v6);
    g.addVertex(v7);
    g.addEdge("Edge1", v0, v1);
    g.addEdge("Edge2", v0, v2);
    g.addEdge("Edge3", v0, v6);
    g.addEdge("Edge4", v0, v3);
    g.addEdge("Edge5", v1, v0);
    g.addEdge("Edge6", v1, v4);
    g.addEdge("Edge7", v2, v0);
    g.addEdge("Edge8", v2, v4);
    g.addEdge("Edge9", v2, v5);

    VisualizationImageServer vs = new VisualizationImageServer(new CircleLayout(g), new Dimension(200, 200));

    JFrame frame = new JFrame();
    frame.getContentPane().add(vs);
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    frame.pack();
    frame.setVisible(true);

我怎样才能按照我想要的方式排列我所有的顶点(它们现在在一个圆圈中)？

如何将顶点名称“A”放在 GUI 中的红色圆圈内，以便显示每个顶点名称。

如何在 GUI 中将每个权重添加到两个顶点之间的线的顶部？

提前致谢

Answer 1

虽然我不熟悉 JUNG，但我已经为我的大学项目 (Source code) 实现了 Dijkstra 算法的 GUI。

它是基于Java Swing 的Graphics2D 对象来绘制边的。由于您已经实现了 Dijkstra 算法，您可能只对下面给出的绘制边(带有箭头和标签的线)的代码感兴趣。它使用三角函数绘制方向箭头。

private void drawLineSegment(Point from, Point to, Color c, int size, String label, Graphics2D g) {
    g.setColor(c);
    g.setStroke(new BasicStroke(size));
    int x1 = from.getX();
    int y1 = from.getY();
    int x2 = to.getX();
    int y2 = to.getY();
    g.drawLine(x1, y1, x2, y2);
    int sx = (int) ((x1 + x2) / 2.1);
    int sy = (int) ((y1 + y2) / 2.1);
    int cx = (int) ((x1 + x2) / 2);
    int cy = (int) ((y1 + y2) / 2);
    int d = 10;
    double angle = Util.angle360(from, to);
    double anglePlus45 = angle + 45;
    if (anglePlus45 > 360)
        anglePlus45 = anglePlus45 % 360;
    double angleMinus45 = angle - 45;
    if (angleMinus45 < 360)
        angleMinus45 = angleMinus45 + 360;
    anglePlus45 = Math.toRadians(anglePlus45);
    angleMinus45 = Math.toRadians(angleMinus45);
    int ax1 = (int) (cx - d * Math.cos(anglePlus45));
    int ay1 = (int) (cy - d * Math.sin(anglePlus45));
    int ax2 = (int) (cx - d * Math.cos(angleMinus45));
    int ay2 = (int) (cy - d * Math.sin(angleMinus45));
    g.drawLine(cx, cy, ax1, ay1);
    g.drawLine(cx, cy, ax2, ay2);
    g.drawString(label, sx, sy);
}

这是在`src/wban/simulate/view/SwingViewer.java 中。如果您有兴趣运行代码，可以下载 runnable jar .项目文档可用here和 here .