用c++分别使用贪心法和分支限界求解图的单 源最短路径

单源最短路径问题可以使用贪心算法或分支限界算法进行求解。

首先，我们来看贪心算法。

贪心算法的思想是每次选择当前最优的决策，直到达到全局最优。在单源最短路径问题中，我们可以从源点开始，每次选择与源点距离最短的未访问过的顶点作为下一个访问的顶点，直到所有顶点都被访问过。

以下是使用贪心算法求解单源最短路径的C++代码：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

// 定义图的邻接表表示方式
typedef struct node {
    int v;      // 目标顶点
    int w;      // 边权重
    node(int _v, int _w) : v(_v), w(_w) {}
} Node;

typedef vector<vector<Node>> Graph;

// 使用贪心算法求解最短路径
void dijkstra(const Graph& g, int s, vector<int>& dist) {
    int n = g.size();
    dist.assign(n, INT_MAX);
    dist[s] = 0;
    vector<bool> visited(n, false);

    // 使用优先队列存储未访问的顶点，并按照距离从小到大排序
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, s));

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        if (visited[u]) continue;
        visited[u] = true;

        for (auto& node : g[u]) {
            int v = node.v;
            int w = node.w;

            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
}

int main() {
    int n, m, s;    // n：顶点数，m：边数，s：源点
    cin >> n >> m >> s;

    Graph g(n);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back(Node(v, w));
    }

    vector<int> dist;
    dijkstra(g, s, dist);

    for (int i = 0; i < n; i++) {
        cout << dist[i] << " ";
    }
    cout << endl;

    return 0;
}

接下来，我们来看分支限界算法。

分支限界算法是一种搜索算法，它通过搜索状态空间来找到最优解。在单源最短路径问题中，我们可以将搜索状态定义为从源点到某个未访问过的顶点的路径，每次扩展状态时，我们把当前路径上的边权重之和加上当前顶点到其他未访问过顶点的最小距离，得到一个下界，然后以这个下界为优先级，将状态加入到优先队列中进行扩展。

以下是使用分支限界算法求解单源最短路径的C++代码：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

// 定义图的邻接表表示方式
typedef struct node {
    int v;      // 目标顶点
    int w;      // 边权重
    node(int _v, int _w) : v(_v), w(_w) {}
} Node;

typedef vector<vector<Node>> Graph;

// 使用分支限界算法求解最短路径
void dijkstra(const Graph& g, int s, vector<int>& dist) {
    int n = g.size();
    dist.assign(n, INT_MAX);
    dist[s] = 0;

    // 定义状态类
    class State {
    public:
        int u;              // 当前顶点
        int d;              // 当前距离
        vector<bool> used;  // 记录哪些顶点已经被访问过

        State(int _u, int _d, const vector<bool>& _used) : u(_u), d(_d), used(_used) {}
    };

    // 定义状态比较类
    class StateCompare {
    public:
        bool operator()(const State& s1, const State& s2) const {
            return s1.d > s2.d;
        }
    };

    // 使用优先队列存储搜索状态，并按照下界从小到大排序
    priority_queue<State, vector<State>, StateCompare> pq;
    pq.push(State(s, 0, vector<bool>(n, false)));

    while (!pq.empty()) {
        State state = pq.top();
        pq.pop();

        int u = state.u;
        int d = state.d;
        vector<bool> used = state.used;

        if (d > dist[u]) continue;
        used[u] = true;

        for (auto& node : g[u]) {
            int v = node.v;
            int w = node.w;

            if (!used[v] && d + w < dist[v]) {
                vector<bool> new_used = used;
                new_used[v] = true;
                int new_d = d + w + dist[v];   // 计算下界
                pq.push(State(v, new_d, new_used));
                dist[v] = d + w;
            }
        }
    }
}

int main() {
    int n, m, s;    // n：顶点数，m：边数，s：源点
    cin >> n >> m >> s;

    Graph g(n);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back(Node(v, w));
    }

    vector<int> dist;
    dijkstra(g, s, dist);

    for (int i = 0; i < n; i++) {
        cout << dist[i] << " ";
    }
    cout << endl;

    return 0;
}

以上是使用贪心算法和分支限界算法求解单源最短路径的C++代码，希望对你有所帮助。