Графы

void Djekstra(int s, int n, const vector<vector<pair<int, int>>>& neighbors, vector<int>& out_dist, vector<int>& out_prev)
{
    out_dist.resize(n, INT32_MAX);
    out_prev.resize(n, -1);
    priority_queue<pair<int, int>> que;
    out_dist[s] = 0;
    que.push({ 0,s });
    vector<bool> pass(n, 0);
    while (que.size())
    {
        int v = que.top().second;
        pass[v] = 1;
        que.pop();
        for (auto& u : neighbors[v])
        {
            if (out_dist[v] + u.second < out_dist[u.first])
            {
                out_dist[u.first] = out_dist[v] + u.second;
                out_prev[u.first] = v;
                que.push({ -out_dist[u.first], u.first });
            }
        }
        while (que.size() && pass[que.top().second]) que.pop();
    }
}

struct edge
{
    int u, v, cost;
};

int Ford_Bellmann(int s, int n, const vector<edge>& edges, vector<int>& out_dist, vector<int>& out_prev)
{
    out_dist.resize(n, INT32_MAX);
    out_prev.resize(n, -1);
    out_dist[s] = 0;
    int i = 0;
    int updated;
    for (i = 0; i < n; i++)
    {
        updated = -1;
        for (auto& ed : edges)
        {
            if (out_dist[ed.u]<INT32_MAX && out_dist[ed.v] > out_dist[ed.u] + ed.cost)
            {
                updated = ed.v;
                out_dist[ed.v] = out_dist[ed.u] + ed.cost;
                out_prev[ed.v] = ed.u;
            }
        }
        if (updated >= 0)
            break;
    }
    return updated;
}


void Floyd_Warshall(int n, const vector<vector<int>>& init_d, vector<vector<int>>& out_d, vector<vector<int>>& out_p)
{
    out_d = init_d;
    out_p = vector<vector<int>>(n, vector<int>(n, -1));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++)
                if (out_d[i][k] < INT32_MAX && out_d[k][j] < INT32_MAX && out_d[i][j] > out_d[i][k] + out_d[k][j])
                {
                    out_p[i][j] = k;
                    out_d[i][j] = out_d[i][k] + out_d[k][j];
                }
}

void get_path_Floyd_Warshall(int i, int j, vector<int>& out_path, const vector<vector<int>>& p)
{
    int k = p[i][j];
    if (k < 0)
        return;
    get_path_Floyd_Warshall(i, k, out_path, p);
    out_path.push_back(k);
    get_path_Floyd_Warshall(k, j, out_path, p);
}
void get_path_Floyd_Warshall_start(int i, int j, vector<int>& out_path, const vector<vector<int>>& p)
{
    out_path = { i };
    get_path_Floyd_Warshall(i, j, out_path, p);
    out_path.push_back(j);
}