algoritmul lui johnson

#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<algorithm>
#include<functional>
#define MAX_SIZE 3000
#define INF 999

typedef std::vector<int> vector;
typedef std::pair<int, int> p;
vector vis;
vector g[MAX_SIZE];   //the graph stored in an adjacency matrix
int  n, m;    //n- no of vertices, m -no of edges
std::vector<std::pair<int, int>> dist;  //first to store the distance
                                        //second to store the parent
int source;
void read()
{
    std::ifstream in("file.txt");
    if (!in.is_open())
        std::cout << "Unable to open the file!\n";
    else
    {
        int x, y, w;
        in >> n >> m;
        in >> source;
        for (long long int i = 0; i < n; i++)
            g[i].assign(n, -1);

        for (long long int i = 0; i < m; i++)
        {
            in >> x >> y >> w;
            g[x][y] = w;
        }
    }
}
void init_dist()
{
    for (int i = 0; i <= n; i++)
    {
        dist.push_back({ INF,-1 });
        //here NIL parent is -1
    }
}
bool belman_ford(int source)
{
    int traverse;
    init_dist();
    dist[source] = { 0,-1 };
    for (int i = 1; i<n; i++)
        for (int j = 1; j <n; j++)
        {
            traverse = 1;
            while (traverse <n)
            {
                if (dist[j].first != INF)
                {
                    //checking for relaxation
                    if (g[j][traverse] != -1 && dist[traverse].first > dist[j].first + g[j][traverse])
                    {
                        dist[traverse].first = dist[j].first + g[j][traverse];
                        dist[traverse].second = j;
                    }
                }
                ++traverse;
            }
        }
    //checking for negative cicles
    for (int i = 1; i <n; i++)
    {
        traverse = 1;
        while (traverse <n)
        {
            if (g[i][traverse] != -1 && dist[i].first + g[i][traverse] < dist[traverse].first)
            {
                return false;
            }
            ++traverse;
        }
    }
    return true;
}
void change_matrix()
{

    vector g_[MAX_SIZE];
    for (int i = 0; i <= n + 1; i++)
        g_[i].assign(n + 1, 0);
    //create the g_ graph which includes the source
    //change the iteration to put the source on the 0 position
    for (int i = 0; i <= n; i++)
    {
        g_[0][i] = 0;
        g_[i][0] = 0;
        //here 0 will be -1
    }
    for (int i = 0; i<n; i++)
        for (int j = 0; j<n; j++)
            g_[i + 1][j + 1] = g[i][j];
    g->resize(n + 1);
    for (int i = 0; i <= n; i++)
        g[i].resize(n + 1);
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            g[i][j] = g_[i][j];
}
void dijkstra(int source)
{
    std::priority_queue<p, std::vector<p>, std::greater<p>> Q;
    dist[source].first = 0;
    Q.push({ 0,source });
    while (!Q.empty())
    {
        int a = Q.top().second;
        Q.pop();
        for (int j = 1; j <n; j++)
        {
            if (g[a][j] != -1 && dist[j].first > dist[a].first + g[a][j])
            {
                dist[j].first = dist[a].first + g[a][j];
                Q.push({ dist[j].first,j });
            }
        }


    }
}
void johnson(int source)
{
    /*std::cout << "before adding source\n";
    for (int i = 0; i<n; i++)
    {
        for (int j = 0; j<n; j++)
            std::cout << g[i][j] << " ";
        std::cout << std::endl;
    }*/
    change_matrix();
    /*std::cout << "after adding source\n";
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= n; j++)
            std::cout << g[i][j] << " ";
        std::cout << std::endl;
    }*/
    n += 1;
    if (belman_ford(source))
    {

        for (int k = 0; k<n; k++)
            std::cout << dist[k].first << " " << dist[k].second << ";";
        for (int i = 1; i < n; i++)
            for (int j = 1; j <n; j++)
                //if (g[i][j] == 0)
                g[i][j] += dist[i].first - dist[j].first;

        std::cout << "after belman_ford:\n";
        for (int i = 0; i<n; i++)
        {
            for (int j = 0; j<n; j++)
                std::cout << g[i][j] << " ";
            std::cout << std::endl;
        }
        init_dist();
        dist[source].first = 0;
        dijkstra(source);
    }
    else
        std::cout << "The graph contains negative cicles!\n";
}
int main()
{
    read();
    johnson(source);
    std::cout << "The minimum distances from " << source << " to every following nodes are:\n";
    for (int i = 1; i <n; i++)
        std::cout << "node:" << i << " distance:" << dist[i].first << " parent:" << dist[i].second << "\n";

    return 0;
}