Код неправильно расчитывает расстояние до 3 и 4 вершин графа

У меня есть код:

#include<iostream>
#include<vector>
#include<fstream>
using namespace std;

struct kr {
    int w2;
    int wg;
};

typedef vector<vector<kr> > tgraf;

void Cz(tgraf &Gr){
    int n, m, w1;
    kr kraw;
    ifstream we("AnGrzpAlDi.txt");
    we >> n >> m;
    Gr.resize(n);
    for (int i=0; i<m; i++){
        we >> w1 >> kraw.w2 >> kraw.wg;
        Gr[w1].push_back(kraw);
    }
    we.close();
}

void Dij(tgraf &Gr, int pocz, vector<int> &Ksz){
    kr kraw;
    int i=0, j=0, k, w1;
    vector<bool> Odw;
    Odw.resize(Gr.size(), false);
    Ksz[pocz] = 0;
    for (i=0; i<Gr.size()-1; i++){
        k = 0;
        while (Odw[k]) k++;
        w1 = k;
        for (j=k+1; j<Gr.size(); j++){
            if (!Odw[j] && Ksz[j]<Ksz[w1] + kraw.wg) w1 = j;
        }
        Odw[w1] = true;
        for (j=0; j<Gr[w1].size(); j++){
            kraw = Gr[w1][j];
            if (!Odw[kraw.w2] && (Ksz[w1]+kraw.wg)< Ksz[kraw.w2])
                Ksz[kraw.w2] = Ksz[w1] + kraw.wg;

        }
    }
}

int main(){
    tgraf Gr;
    Cz(Gr);int i=0;
    vector<int> Ksz;
    Ksz.resize(Gr.size(), 1000);
    int pocz;
    cout <<"Num wierz pocz: ";
    cin>>pocz;
    Dij(Gr, pocz, Ksz);
    cout<<"Koszt dojscia z wierz "<<pocz<<" do wierz: "<<endl;
    for (i=0; i<Gr.size(); i++){
        if (i!=pocz){
            cout<<i<<": "<<Ksz[i]<<endl;
        }
    }
    return 0;
}

И у меня есть текстовая запись графа с весом и направлениями:

7 10
0 1 2
0 5 3
1 0 2
1 2 4
1 6 3
3 1 4
3 6 3
4 1 2
4 3 5
5 1 1
5 4 4

Код верно определяет цену дохода до всех вершин, кроме 3 и 4. Он пишет что дойти туда вовсе не возможно(появляется запись 3: 1000, 4: 1000), хотя это поидее не так. Я пыталась выпытать у ИИ где ошибка, но так ничего и не добилась.


Ответы (1 шт):

Автор решения: Harry

В первой строке данных у вас записано, что есть 10 ребер. Если их посчитать, то последнее, одиннадцатое ребро

5 4 4

останется "за бортом" — единственное, через которое можно попасть в вершину 4, ну, а путь в вершину 3 ведет только из вершины 4.

Так что с вашими исходными данными в вершины 3 и 4 попасть и в самом деле нельзя.

Интересно, это данные, которые вы получили в качестве задания, или сочинили сами? :)

P.S. Правильность кода не смотрел.
P.P.S. ИИ - нашли о чем и кого спрашивать... Мне нынешнее отношение вроде бы умных людей к ИИ напоминает массу историй начала компьютеризации в духе "секретарша кладет рукописный текст на клавиатуру и удивляется, почему компьютер его сам не вводит"...

→ Ссылка