【数学建模实战案例】外卖送餐路径优化：从模型到 C++ 编程-野牛程序员讲少儿编程

? 背景描述

外卖员每天需要送达多个订单，如何选择最优路径，让配送距离最短、用时最少，是一个现实中的优化问题。这个问题其实可以抽象为：

? 给定一个带权图，从起点出发，求到所有配送点的最短路径。

这正是图论中的最短路径问题（Shortest Path Problem），可以用经典的 Dijkstra算法 建模与求解。

? 数学建模思路

? C++ 完整代码

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

// 常量定义：最大节点数量
const int MAXN = 1005;

// 邻接表存图，pair<终点, 权重>
vector<pair<int, int>> graph[MAXN];

// 最短路径数组
int dist[MAXN];

// Dijkstra 算法函数
void dijkstra(int start, int n) {
    // 初始化所有距离为无穷大
    for (int i = 1; i <= n; ++i) dist[i] = INT_MAX;
    dist[start] = 0;

    // 小根堆：pair<当前距离, 当前节点>
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u]) continue; // 剪枝

        for (auto [v, w] : graph[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

// 主函数
int main() {
    int n, m, s;
    cout << "请输入城市点数n、道路数m、起点编号s：" << endl;
    cin >> n >> m >> s;

    cout << "请输入每条道路：起点 终点 距离" << endl;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        // 无向图则需要添加双向边
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }

    dijkstra(s, n);

    cout << "从起点 " << s << " 到所有点的最短距离如下：" << endl;
    for (int i = 1; i <= n; ++i) {
        if (dist[i] == INT_MAX) cout << "点" << i << "：不可达" << endl;
        else cout << "点" << i << "：" << dist[i] << endl;
    }

    return 0;
}

? 示例输入输出

输入：
6 7 1
1 2 4
1 3 2
2 3 1
2 4 5
3 4 8
4 5 3
5 6 6

输出：
从起点 1 到所有点的最短距离如下：
点1：0
点2：3
点3：2
点4：8
点5：11
点6：17

✅ 小结

• 外卖路径优化问题，是经典的图论建模应用；

• 通过Dijkstra算法 + 编程实现，可高效求解最短路径；

• 数学建模与编程结合，是解决现实问题的关键能力。