Shortest path given beginning and end of a weighted graph

Question

I have to read in a file to create a weighted graph. The shortest path must be found using input from the file. File will be structured as first line = numVertices and every line below that has 3 numbers given as : 0 1 2 where 0 is start of an edge, 1 is the end of the edge, and 2 is the weight. I've tried implementing an adjacency matrix when creating my graph but have had no luck. Any suggestions would be greatly appreciated.

Have tried restructuring the way I read in my file and have also tried adjusting my findShortestPath function.

void createGraph(string file_name) //Function to create a graph based on a file, whose name is file_name.
{
    ifstream f(file_name);
    if (f.fail())
    {
        return;
    }
    string line;
    getline(f, line);
    int num = stoi(line);
    numVertices = num;

    int data[50][50];

    string line2;
    int num1 = 0, num2 = 0, num3 = 0;

    while (!f.eof())
    {
        f >> num1;
        f >> num2;
        f >> line2;
        num3 = stoi(line2);
        data[num1][num2] = num3;

    }

}
//////////////////shortest path function

string findShortestPath(int start, int end)
{
    int data[numVertices][numVertices];
    int dist[numVertices];
    bool sptSet[numVertices];
    int parent[numVertices];

    for (int i = 0; i < numVertices; i++)
    {
        parent[0] = -1;
        dist[i] = INT_MAX;
        sptSet[i] = false;
    }

    dist[start] = 0;

    for (int count = 0; count < numVertices - 1; count++)
    {
        int u = minDistance(dist, sptSet);
        sptSet[u] = true;
        if (sptSet[u] == end)
            break;

        for (int v = 0; v < numVertices; v++)
            if (!sptSet[v] && data[u][v] && dist[u] + data[u][v] < dist[v])
            {
                parent[numVertices] = end;
                dist[v] = dist[u] + data[u][v];
            }
    }
    printSolution(parent);

Output is not outputting shortest path and is printing random numbers.

[`while (!f.eof())` is evil.](https://stackoverflow.com/questions/5605125/why-is-iostreameof-inside-a-loop-condition-i-e-while-stream-eof-cons) Consider using `while(f >> num1 >> num2 >> line2;)` instead. It won't enter the loop if any of the inputs fail for any reason. — user4581301, Jul 03 '19 at 23:53
[Fear the VLA.](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard) They are non-portable and potential stack-killers. — user4581301, Jul 03 '19 at 23:57
`string findShortestPath(int start, int end)` promices to return a `string`, but it doesn't look like it does. While a compiler will allow this, usually with a warning, the code it generates is questionable. I recommend replacing the return type with `void` or rethinking the function. — user4581301, Jul 03 '19 at 23:58
Speaking of warnings, a good compiler will tell you almost exactly what is wrong: *warning: variable 'data' set but not used*. Don't ignore the warnings. they are the first line of defense against logic errors. If you research and resolve them when the compiler alerts you to them, you generally save a lot of time debugging. — user4581301, Jul 04 '19 at 00:02

score 0 · Answer 1 · edited Jul 04 '19 at 00:05

0

In your findShortestPath function data[numVertices][numVertices] is not the same as the data variable in your createGraph function.

Look at this https://www.geeksforgeeks.org/scope-of-variables-in-c/ or try finding other sources on scope of variables.

edited Jul 04 '19 at 00:05

user4581301

33,082
7
33
54

answered Jul 03 '19 at 23:49

linjoehan

103
1
5

how could I call the data into findShortestPath? – zman1 Jul 04 '19 at 00:33
you could make data a global variable (declare it outside any functions or main) and remove the declarations in both functions. – linjoehan Jul 04 '19 at 01:11

score 0 · Answer 2 · answered Jul 04 '19 at 01:22

In your function findShortestPath you have declared a local array called data, which is supposed to store the adjacency matrix data. However, you have never written any data into it! Consider passing the matrix as a function argument. Your function signature should look something like this:

findShortestPath(int** data, int numVertices, int start, int end)

Also, avoid using VLA as it is not part of the standard. Consider creating a two dimensional array on the heap using new. (and don't forget to do delete[] after you are done!)

Or you can use std::vector<std::vector<int>>, if you don't want to manage your array's lifetime manually.

It is an assignment and I am not allowed to change the findShortestPath function parameters. Trying to find another way. — zman1, Jul 04 '19 at 01:45
@zman1 Use global variables then. Move your `int data[50][50]` to global scope. — ph3rin, Jul 04 '19 at 01:49

Shortest path given beginning and end of a weighted graph

2 Answers2