Floyd Algorithm in C++ [closed]

Question

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.

Closed 9 years ago.

I'm trying to implement a Floryd Algorithm in C++

I have this already:

a means the node where the edge starts.

b means the node where the edge ends.

t means the time of the edge.

m means the number of edges.

n means the number of nodes.

typedef pair<int,int> nodo;
vector <nodo> g[100000];

void preguntarFloyd()
{
    g->clear();
    int  m;
    int contador = 0;
    cin m;

    for(int k = 0; k < m ; k++)
    {
        int a, b, t;
        cin >> a >> b >> t;
        g[a].push_back(nodo(b,t));
    }

    for (int k = 0; k < n; k++)
    {
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j <n; j++)
            {
                if(g[i][k].second + g[k][j].second < g[i][j].second )
                {
                    g[i][j].second = g[i][k].second + g[k][j].second;
                }
            }
        }
    }


}

When I try the code, the program crashes saying: "Expression: Vector subscript out of range"

I hope you guys can help me since I haven't been able to work this out!

Answer 1

The two most common ways to represent a graph is:

• An adjacency-list
• An adjacency-matrix

You have one data structure, in the initialisation phase you handle it like if it was a an adjacency-list then you try to access it as if it were an adjacency-matrix. Obviously this will never work...