C++实现线段最短路径查找程序，并可视化显示

以下是用C++实现的程序，可以生成随机的线段并找出最短的一条。程序使用了Qt库来创建可执行界面，并使用了QPainter来绘制线段和标记最短路线。

#include <QApplication>
#include <QWidget>
#include <QPushButton>
#include <QMessageBox>
#include <QPainter>
#include <vector>
#include <random>
#include <algorithm>
#include <cmath>

struct Point {
    int x;
    int y;
};

struct Line {
    Point start;
    Point end;
};

class Widget : public QWidget {
public:
    Widget(QWidget *parent = nullptr) : QWidget(parent), n(0), linesGenerated(false) {
        setFixedSize(800, 600);
        setWindowTitle('Shortest Line');

        generateButton = new QPushButton('Generate Lines', this);
        generateButton->setGeometry(10, 10, 120, 30);
        connect(generateButton, &QPushButton::clicked, this, &Widget::generateLines);

        shortestButton = new QPushButton('Find Shortest', this);
        shortestButton->setGeometry(10, 50, 120, 30);
        shortestButton->setEnabled(false);
        connect(shortestButton, &QPushButton::clicked, this, &Widget::findShortest);

        resetButton = new QPushButton('Reset', this);
        resetButton->setGeometry(10, 90, 120, 30);
        resetButton->setEnabled(false);
        connect(resetButton, &QPushButton::clicked, this, &Widget::reset);

        messageBox = new QMessageBox(this);
        messageBox->setStandardButtons(QMessageBox::Ok);
        messageBox->setDefaultButton(QMessageBox::Ok);
        messageBox->setWindowTitle('Result');

        generator.seed(std::random_device()());

        generateLines();
    }

    void generateLines() {
        n = std::uniform_int_distribution<int>(10, 40)(generator);
        lines.clear();

        std::uniform_int_distribution<int> xDist(50, width() - 50);
        std::uniform_int_distribution<int> yDist(150, height() - 50);

        Point startPoint = {50, 50};
        Point endPoint = {width() - 50, height() - 50};

        generateLineSegments(startPoint, endPoint, n);

        linesGenerated = true;
        shortestButton->setEnabled(true);
        resetButton->setEnabled(true);
        update();
    }

    void findShortest() {
        if (!linesGenerated) {
            return;
        }

        Line shortestLine;
        double shortestDistance = std::numeric_limits<double>::max();

        for (const auto& line : lines) {
            double distance = calculateDistance(line);

            if (distance < shortestDistance && !isLineCovered(line)) {
                shortestDistance = distance;
                shortestLine = line;
            }
        }

        if (shortestDistance == std::numeric_limits<double>::max()) {
            messageBox->setText('No shortest line found.');
        } else {
            messageBox->setText(QString('Shortest line found: (%1, %2) - (%3, %4)
Distance: %5')
                                .arg(shortestLine.start.x)
                                .arg(shortestLine.start.y)
                                .arg(shortestLine.end.x)
                                .arg(shortestLine.end.y)
                                .arg(shortestDistance));
        }

        messageBox->show();
    }

    void reset() {
        linesGenerated = false;
        shortestButton->setEnabled(false);
        resetButton->setEnabled(false);
        update();
    }

protected:
    void paintEvent(QPaintEvent *) override {
        QPainter painter(this);

        painter.setPen(Qt::black);

        if (linesGenerated) {
            for (const auto& line : lines) {
                painter.drawLine(line.start.x, line.start.y, line.end.x, line.end.y);
            }

            if (shortestButton->isEnabled()) {
                Line shortestLine;
                double shortestDistance = std::numeric_limits<double>::max();

                for (const auto& line : lines) {
                    double distance = calculateDistance(line);

                    if (distance < shortestDistance && !isLineCovered(line)) {
                        shortestDistance = distance;
                        shortestLine = line;
                    }
                }

                painter.setPen(Qt::red);
                painter.setBrush(Qt::red);
                painter.setRenderHint(QPainter::Antialiasing, true);
                painter.setRenderHint(QPainter::HighQualityAntialiasing, true);
                painter.setRenderHint(QPainter::TextAntialiasing, true);
                painter.setRenderHint(QPainter::SmoothPixmapTransform, true);
                painter.setRenderHint(QPainter::NonCosmeticDefaultPen, true);
                painter.setRenderHint(QPainter::Qt4CompatiblePainting, true);
                painter.setRenderHint(QPainter::LosslessImageRendering, true);
                painter.setRenderHint(QPainter::Antialiasing, true);
                painter.setRenderHint(QPainter::TextAntialiasing, true);
                painter.setRenderHint(QPainter::SmoothPixmapTransform, true);

                painter.drawLine(shortestLine.start.x, shortestLine.start.y, shortestLine.end.x, shortestLine.end.y);
            }
        }
    }

private:
    void generateLineSegments(const Point& startPoint, const Point& endPoint, int n) {
        std::uniform_int_distribution<int> dist(0, 1);

        Point currentPoint = startPoint;

        for (int i = 0; i < n; ++i) {
            Line line;
            line.start = currentPoint;

            if (i == n - 1) {
                line.end = endPoint;
            } else {
                Point nextPoint;
                nextPoint.x = std::uniform_int_distribution<int>(currentPoint.x - 100, currentPoint.x + 100)(generator);
                nextPoint.y = std::uniform_int_distribution<int>(currentPoint.y - 100, currentPoint.y + 100)(generator);
                line.end = nextPoint;
                currentPoint = nextPoint;
            }

            lines.push_back(line);
        }
    }

    double calculateDistance(const Line& line) {
        return std::sqrt(std::pow(line.start.x - line.end.x, 2) + std::pow(line.start.y - line.end.y, 2));
    }

    bool isLineCovered(const Line& line) {
        for (const auto& otherLine : lines) {
            if (line.start.x == otherLine.start.x &&
                line.start.y == otherLine.start.y &&
                line.end.x == otherLine.end.x &&
                line.end.y == otherLine.end.y) {
                continue;
            }

            if (line.start.x >= otherLine.start.x && line.start.x <= otherLine.end.x &&
                line.start.y >= otherLine.start.y && line.start.y <= otherLine.end.y &&
                line.end.x >= otherLine.start.x && line.end.x <= otherLine.end.x &&
                line.end.y >= otherLine.start.y && line.end.y <= otherLine.end.y) {
                return true;
            }
        }

        return false;
    }

    int n;
    std::vector<Line> lines;
    std::default_random_engine generator;
    QPushButton *generateButton;
    QPushButton *shortestButton;
    QPushButton *resetButton;
    QMessageBox *messageBox;
    bool linesGenerated;
};

int main(int argc, char *argv[]) {
    QApplication app(argc, argv);
    Widget w;
    w.show();
    return app.exec();
}