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

Question

#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] = shortest path between vertice i and vertice j.

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

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

Answer 1

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

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

的组合复杂度

虽然函数调用的复杂度是 O(E)，但您的 shortest_path 数组有 V^2 个元素，因此单独创建数组是 O(V^2).

Answer 2

请注意，j 在函数调用中没有变化，因此函数的复杂度仅取决于 i。

shortest_path[i][j] = min_path 正在完成两件事：保存从 i 到 j 的最小路径并标记 i 已访问（因为 j 没有改变）。因此访问过的顶点将不会再次访问。

所以 shortest_path 将被称为不同的值 i 可以让我们称之为 N 这是图中顶点的总数。因此，最小时间复杂度至少为 O(N)。在每次调用中，for 循环运行 outdegree of vertex i。现在加上所有顶点的 for 循环成本，它将是 outdegree of V1 + outdegree of V2 + ... + outdegree of Vn 等于 O(E)。因此总时间复杂度为 O(N + E)

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

Shortest path between 2 nodes in DAG unweighed

c++

graph

shortest-path