分支限界法最短单源路径

min_path.cpp

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

struct Node {
    int number;
    int distance;
};

bool operator<(Node a, Node b)
{
    if (a.distance > b.distance)
        return true;
    else
        return false;
}

struct Edge {
    int dst;
    int distance;
};

struct Point {
    int number;
    Edge *edges;
    int nEdges;
};


int *min_path;

int main()
{
    int N = 10;
    int graph[N+1][N+1];
    min_path = new int[N+1];
    Point *points = new Point[N + 1];
    for (int i = 1; i <= 10; i++)
        for (int j = 1; j <= 10; j++)
            cin >> graph[i][j];

    for (int i = 1; i <= 10; i++) {
        points[i].number = i;
        int count = 0;
        for (int j = 1; j <= 10; j++) {
            if (graph[i][j] > 0)
                count++;
        }
        points[i].edges = new Edge[count];
        points[i].nEdges = count;
        count = 0;
        for (int j = 1; j <= 10; j++) {
            if(graph[i][j] > 0) {
                points[i].edges[count].dst = j;
                points[i].edges[count].distance = graph[i][j];
                count++;
            }
        }
    }

    priority_queue<Node> queue;
    min_path[1] = 0;
    for (int i = 2; i <= 10; i++)
        min_path[i] = 9999;

    Node flag_node;
    flag_node.number = points[1].number;
    flag_node.distance = 0;
    queue.push(flag_node);
    while(!queue.empty())
    {
        flag_node = queue.top();
        queue.pop();
        Node *createNode;
        for (int i = 0; i < points[flag_node.number].nEdges; i++) {
            createNode = new Node;
            createNode->number = points[flag_node.number].edges[i].dst;
            createNode->distance = flag_node.distance + points[flag_node.number].edges[i].distance;
            if(createNode->distance < min_path[createNode->number]) {
                min_path[createNode->number] = createNode->distance;
                queue.push(*createNode);
            }
        }
    }

    for (int i = 1; i <= 10; i++) {
        cout << "The min distance to "
             << i
             << " is "
             << min_path[i]
             << endl;
    }
    return 0;
}