Кратчайший путь с учетом начала и конца взвешенного графика

Question

Мне нужно прочитать файл, чтобы создать взвешенный график.Кратчайший путь должен быть найден с использованием входных данных из файла.Файл будет структурирован как первая строка = numVertices и каждая строка ниже имеет 3 числа, заданные как: 0 1 2, где 0 - начало ребра, 1 - конец ребра и 2 - вес.Я пытался реализовать матрицу смежности при создании графа, но мне не повезло.Будем очень благодарны за любые предложения.

Попытка реструктурировать способ, которым я читаю в моем файле, а также попытка настроить функцию findShortestPath.

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);

Вывод не выводит кратчайший путь и печатаетслучайные числа.

Answer 1

В вашей функции findShortestPath вы объявили локальный массив с именем data, который должен хранить данные матрицы смежности.Тем не менее, вы никогда не записывали в него никаких данных!Рассмотрим передачу матрицы в качестве аргумента функции.Ваша подпись функции должна выглядеть примерно так:

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

Кроме того, избегайте использования VLA, поскольку это не является частью стандарта.Попробуйте создать двумерный массив в куче, используя new.(и не забудьте сделать delete[] после того, как закончите!)

Или вы можете использовать std::vector<std::vector<int>>, если не хотите управлять временем жизни вашего массива вручную.

Answer 2

В вашей findShortestPath функции data[numVertices][numVertices] отличается от переменной data в вашей createGraph функции.

Посмотрите на это https://www.geeksforgeeks.org/scope-of-variables-in-c/ или попробуйте найти другие источники наобласть видимости переменных.