Кратчайший путь между двумя узлами в DAG не взвешен

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.

shorttest_path [i] [j] = кратчайший путь между версией i и версией j.

В чем сложность функции int shortestPath(int i, int j)?

Я думаю, это O (V + E), где V - количество вершин и E - число ребер, но я не знаю, как докажите это.

Answer 1

Обратите внимание, что j не изменяется в вызове функции, поэтому сложность функции зависит только от i.

shortest_path[i][j] = min_path выполняет две вещи: сохранение минимального пути от i до j и отметка i посещенных (так как j не меняется). Следовательно, однажды посещенная вершина больше не будет посещена.

Так что shortest_path будет вызываться для различных значений i можно принять, назовем ее N, которая является общим числом вершин в графе. Поэтому минимальная временная сложность будет по крайней мере O(N). Внутри каждого вызова для l oop работает для outdegree of vertex i. Теперь, добавив к стоимости l oop всех вершин, это будет outdegree of V1 + outdegree of V2 + ... + outdegree of Vn, что равно O(E). Следовательно, общая сложность времени составляет O(N + E)

Answer 2

Если мы не учитываем вызовы, где расстояние от текущего узла уже вычислено, очевидно, что существует не более V вызовов функций. Сложность вызова функции, игнорирующего рекурсивные вызовы, является линейной по отношению к количеству соседей узла, поэтому общая сложность этих вызовов составляет O(E).

Для вызовов, в которых расстояние текущего узла уже вычислено, для каждого ребра графа происходит постоянное число этих вызовов, поэтому сложность составляет O(E). Это дает совокупную сложность O(E).

Хотя сложность вызова функции равна O(E), ваш массив shortest_path содержит V^2 элементов, поэтому создание только одного массива O(V^2).