图论最短路径问题

图论中的图（Graph）是由若干给定的点及连接两点的线所构成的图形，通常用来事物之间的特定关系。一个图可以用数学语言描述为 $G(V(G),E(G))$。V(vertex) 指的是图的顶点集，E(edge) 指的是图的边集。

根据边是否有方向，可将图分为有向图和无向图，有些图的边上有权重值，这样的图成为有权图。

Dijkstra 算法

具体 C++ 代码：

// Calculate The Shortest Distance Between The Starting And The Ending Node
    int calculate(int start, int end) {
        vector<bool> visited(nodeCnt + 1);
        vector<int> d(nodeCnt + 1);
        vector<int> waiting;

        int curr = start;

        // Initialize
        for(int i = 1; i <= nodeCnt; i++) {
            d[i] = 0;
            visited[i] = 0;
        }

        while(curr != end) {
            Node* currNode = graph[curr];
            visited[curr] = true;
            for(int i = 0; i < currNode->ptr.size(); i++) {
                if(visited[currNode->ptr[i]->id] == false) {
                    printf("从节点 %d 到 %d 距离 %d\n", curr, currNode->ptr[i]->id, currNode->distance[i]);
                    if(d[currNode->ptr[i]->id] == 0) {
                        waiting.push_back(currNode->ptr[i]->id);
                        d[currNode->ptr[i]->id] = d[curr] + currNode->distance[i];
                    } else {
                        d[currNode->ptr[i]->id] = min(d[currNode->ptr[i]->id], d[curr] + currNode->distance[i]);
                    }
                }
            }

            printf("=====================Information====================");
            printf("\nid      : ");
            for(int i = 1; i < d.size(); i++) printf("%3d ", i);
            printf("\ndistance: ");
            for(int i = 1; i < d.size(); i++) printf("%3d ", d[i]);
            printf("\nvisited : ");
            for(int i = 1; i < d.size(); i++) printf("%3d ", visited[i] ? 1 : 0);
            printf("\n====================================================\n");
            printf("Waiting Queue: ");
            for(int i = 0; i < waiting.size(); i++) printf("%3d", waiting[i]);
            printf("\n");

            if(waiting.size() == 0) return -1;

            vector<int>::iterator itor;
            vector<int>::iterator target = waiting.begin();
            for(itor = waiting.begin(); itor != waiting.end(); itor++) {
                if(d[*itor] < d[*target] && visited[*itor] == false) target = itor;
            }
            curr = *target;
            waiting.erase(target);
        }
        return d[end];
    }

完整代码到文末，代码并没有为节点的父节点进行记录，有需要可自行添加。

Matlab 中求最短路径

[P, d] = shortestpath(G, start, end [, 'Method', algorithm]);

G为输入图，start和end分别是起点和终点，Method和algorithm是可选的参数，分别代表最短路径的算法，一般不用特别设置。返回值 P 和 d 分别是最短路径经过的节点以及其最短距离。

Matlab 中返回任意两点的距离矩阵

d = distances(G [,'Method', algorithm]);

返回一个 NxN 的矩阵，代表点 i 到点 j 的距离。

Matlab 中返回给定范围内的所有点

[nodeIDs, dist] = nearest(G, s, d [, 'Method', algorithm]);

nodeIDs 就是范围内的节点的 ID，dist 就是距离。

Dijkstra 算法完整代码部分

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<map>
#include<unordered_map>

using namespace std;

class Node {
public:
    int id;
    vector<Node *> ptr;
    vector<int> distance;
    Node(int id) : id(id) {}
};

class Graph{
private:
    int nodeCnt = 0;
    unordered_map<int, Node *> graph;

public:
    // Insert A Node To Graph
    bool insert(int id) {
        if(graph.find(id) != graph.end()) return false;

        graph[id] = new Node(id);
        nodeCnt = max(id, nodeCnt);
        return true;
    }
    
    // Connect Two Nodes On The Graph
    bool connect(int node1, int node2, int distance, bool oneWay = true) {
        if(graph.find(node1) == graph.end()) return false;
        if(graph.find(node2) == graph.end()) return false;
        
        graph[node1]->ptr.push_back(graph[node2]);
        graph[node1]->distance.push_back(distance);
        if(oneWay) return true;
        
        graph[node2]->ptr.push_back(graph[node1]);
        graph[node2]->distance.push_back(distance);
        return true;
    }

    // Calculate The Shortest Distance Between The Starting And The Ending Node
    int calculate(int start, int end) {
        vector<bool> visited(nodeCnt + 1);
        vector<int> d(nodeCnt + 1);
        vector<int> waiting;

        int curr = start;

        // Initialize
        for(int i = 1; i <= nodeCnt; i++) {
            d[i] = 0;
            visited[i] = 0;
        }
        
        while(curr != end) {
            Node* currNode = graph[curr];
            visited[curr] = true;
            for(int i = 0; i < currNode->ptr.size(); i++) {
                if(visited[currNode->ptr[i]->id] == false) {
                    printf("从节点 %d 到 %d 距离 %d\n", curr, currNode->ptr[i]->id, currNode->distance[i]);
                    if(d[currNode->ptr[i]->id] == 0) {
                        waiting.push_back(currNode->ptr[i]->id);
                        d[currNode->ptr[i]->id] = d[curr] + currNode->distance[i];
                    } else {
                        d[currNode->ptr[i]->id] = min(d[currNode->ptr[i]->id], d[curr] + currNode->distance[i]);
                    }
                }
            }

            printf("=====================Information====================");
            printf("\nid      : ");
            for(int i = 1; i < d.size(); i++) printf("%3d ", i);
            printf("\ndistance: ");
            for(int i = 1; i < d.size(); i++) printf("%3d ", d[i]);
            printf("\nvisited : ");
            for(int i = 1; i < d.size(); i++) printf("%3d ", visited[i] ? 1 : 0);
            printf("\n====================================================\n");
            printf("Waiting Queue: ");
            for(int i = 0; i < waiting.size(); i++) printf("%3d", waiting[i]);
            printf("\n");

            if(waiting.size() == 0) return -1;

            vector<int>::iterator itor;
            vector<int>::iterator target = waiting.begin();
            for(itor = waiting.begin(); itor != waiting.end(); itor++) {
                if(d[*itor] < d[*target] && visited[*itor] == false) target = itor;
            }
            curr = *target;
            waiting.erase(target);
        }
        return d[end];
    }
};

int main() {
    Graph* g = new Graph();
    char c = 'w';
    int node1, node2, distance, oneWay;
    scanf("%c", &c);
    while(c != 'e') {
        switch(c) {
            case 'i':
                scanf("%d", &node1);
                if(g->insert(node1)) {
                    printf("插入节点 %d 成功\n", node1);
                } else {
                    printf("插入节点 %d 失败\n", node1);
                }
            break;
            case 'c':
                scanf("%d %d %d %d", &node1, &node2, &distance, &oneWay);
                if(g->connect(node1, node2, distance, (oneWay) ? true : false)) {
                    printf("连接节点 %d 到 %d 成功，距离 %d，方向 %s\n", node1, node2, distance, (oneWay) ? "单向" : "双向");
                } else {
                    printf("连接节点 %d 到 %d 失败。\n", node1, node2);
                }
            break;
            case 'd':
                scanf("%d %d", &node1, &node2);
                printf("节点 %d 到 %d 的距离为（-1为无法到达）：%d\n", node1, node2, g->calculate(node1, node2));
            break;
        }
        scanf("%c", &c);
    }
    return 0;
}