Java 实现：在两点之间生成随机折线并找出最短路径

以下是实现该功能的 Java 代码：

import java.awt.*;
import java.awt.event.*;
import java.awt.geom.Line2D;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import javax.swing.*;

public class ShortestPath extends JFrame {
    private static final int WIDTH = 800;
    private static final int HEIGHT = 600;
    private static final int POINT_RADIUS = 6;
    private static final int LINE_WIDTH = 3;
    private static final Color POINT_COLOR = Color.RED;
    private static final Color LINE_COLOR = Color.BLACK;
    private static final Color SHORTEST_LINE_COLOR = Color.BLUE;

    private List<Point> points;
    private List<Line2D> lines;
    private List<Line2D> shortestPath;

    public ShortestPath() {
        setTitle('Shortest Path Finder');
        setSize(WIDTH, HEIGHT);
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        setLocationRelativeTo(null);
        setResizable(false);

        points = new ArrayList<>();
        lines = new ArrayList<>();
        shortestPath = new ArrayList<>();

        JPanel panel = new JPanel() {
            @Override
            protected void paintComponent(Graphics g) {
                super.paintComponent(g);
                Graphics2D g2d = (Graphics2D) g;

                // 绘制线段
                for (Line2D line : lines) {
                    g2d.setStroke(new BasicStroke(LINE_WIDTH));
                    g2d.setColor(LINE_COLOR);
                    g2d.draw(line);
                }

                // 绘制最短路线
                for (Line2D line : shortestPath) {
                    g2d.setStroke(new BasicStroke(LINE_WIDTH));
                    g2d.setColor(SHORTEST_LINE_COLOR);
                    g2d.draw(line);
                }

                // 绘制点
                g2d.setColor(POINT_COLOR);
                for (Point point : points) {
                    int x = (int) point.getX();
                    int y = (int) point.getY();
                    g2d.fillOval(x - POINT_RADIUS, y - POINT_RADIUS, POINT_RADIUS * 2, POINT_RADIUS * 2);
                }
            }
        };

        panel.addMouseListener(new MouseAdapter() {
            @Override
            public void mouseClicked(MouseEvent e) {
                if (e.getButton() == MouseEvent.BUTTON1) {
                    Point point = e.getPoint();
                    points.add(point);
                    repaint();
                } else if (e.getButton() == MouseEvent.BUTTON3) {
                    generateLines();
                    findShortestPath();
                    repaint();
                }
            }
        });

        add(panel);
    }

    private void generateLines() {
        lines.clear();

        int numLines = (int) (Math.random() * 31) + 10; // 生成10-40条线段
        for (int i = 0; i < numLines; i++) {
            Point p1 = points.get((int) (Math.random() * points.size()));
            Point p2 = points.get((int) (Math.random() * points.size()));
            Line2D line = new Line2D.Double(p1, p2);
            lines.add(line);
        }
    }

    private void findShortestPath() {
        shortestPath.clear();

        List<Line2D> sortedLines = new ArrayList<>(lines);
        Collections.sort(sortedLines, (line1, line2) -> {
            double length1 = line1.getP1().distance(line1.getP2());
            double length2 = line2.getP1().distance(line2.getP2());
            return Double.compare(length1, length2);
        });

        for (Line2D line : sortedLines) {
            boolean isBlocked = false;
            for (Line2D otherLine : sortedLines) {
                if (otherLine != line && otherLine.intersectsLine(line)) {
                    isBlocked = true;
                    break;
                }
            }
            if (!isBlocked) {
                shortestPath.add(line);
                break;
            }
        }
    }

    public static void main(String[] args) {
        SwingUtilities.invokeLater(() -> {
            ShortestPath shortestPath = new ShortestPath();
            shortestPath.setVisible(true);
        });
    }
}

运行该程序，点击窗口中的位置添加点，右键点击窗口重新生成线段，并找到最短路径，并在窗口中显示。