时间戳

首页 > 解决方案 > DAG 中 2 个节点之间的最短路径未加权

c++ - DAG 中 2 个节点之间的最短路径未加权

问题描述

#include <bits/stdc++.h>

#define MAX_NODES 1005
#define INFINITE 
using namespace std;

vector<int> graph[MAX_NODES];
int numOfVertices, numOfEdges;

int shortest_path[MAX_NODES][MAX_NODES]; // shortest_path[i][j] holds the shortest path between i and j

int k;

int shortestPath(int i, int j) {
    // k ++;
    if (i == j) 
        shortest_path[i][j] = 1;

    // if we didn't solve shortest_path between i and j before

        // than solve it
    if (!shortest_path[i][j]) {

        int min_path = 10e6;
        for (auto vertice : graph[i])
            min_path = min(min_path, shortestPath(vertice, j) + 1);


        shortest_path[i][j] = min_path;
    }
    return shortest_path[i][j];
}

// the graph will be directed
void read() {
    int x, y; // temporary variables to read vertices and store them in our "graph"
    cin >> numOfVertices >> numOfEdges;

    for (int i = 0;i < numOfEdges;i ++) {
        cin >> x >> y;
        graph[x].push_back(y);
    }
}

void print() {
    for (int i = 0;i < numOfVertices;i ++) {
        if (graph[i].size())
            cout << i << " : ";
        for (int j = 0;j < graph[i].size();j ++) {
            cout << graph[i][j] << ' ';
        }
        if (graph[i].size())
            cout << '\n';
    }
}


int main() {
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);

    // ios_base :: sync_with_stdio(false);
    // cin.tie(NULL);
    // cout.tie(NULL);

    read();
    // print();

    int i = 1;
    int j = 7;
    int answer = shortestPath(i, j);

    if (answer == 10e6)
        printf("There are no paths between vertice %d and vertice %d\n", i, j);
    else
        printf("Shortest path between vertice %d and vertice %d ins: %d\n", i, j, answer - 1);

    // cout << k << endl;
    return 0;
}

上述程序计算未加权 DAG 中 2 个顶点之间的最短路径。

shortest_path[i][j] = 顶点 i 和顶点 j 之间的最短路径。

函数的复杂度是int shortestPath(int i, int j)多少？

我认为是 O(V + E) 其中 V 是顶点数和 E 边数，但我不知道如何证明它。

标签： c++graphshortest-path

解决方案

如果我们不计算已经计算出当前节点距离的调用，显然最多有V函数调用。忽略递归调用的函数调用的复杂度与节点的邻居数成线性关系，因此这些调用的总复杂度为O(E).

对于已经计算出当前节点距离的调用，图中每条边都会发生恒定数量的调用，因此复杂度为O(E). 这给出了 的组合复杂度O(E)。

尽管函数调用的复杂性是O(E)，您的shortest_path数组有V^2元素，所以单独创建数组是O(V^2)。

推荐阅读