Код неправильно расчитывает расстояние до 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 шт):
В первой строке данных у вас записано, что есть 10 ребер. Если их посчитать, то последнее, одиннадцатое ребро
5 4 4
останется "за бортом" — единственное, через которое можно попасть в вершину 4, ну, а путь в вершину 3 ведет только из вершины 4.
Так что с вашими исходными данными в вершины 3 и 4 попасть и в самом деле нельзя.
Интересно, это данные, которые вы получили в качестве задания, или сочинили сами? :)
P.S. Правильность кода не смотрел.
P.P.S. ИИ - нашли о чем и кого спрашивать... Мне нынешнее отношение вроде бы умных людей к ИИ напоминает массу историй начала компьютеризации в духе "секретарша кладет рукописный текст на клавиатуру и удивляется, почему компьютер его сам не вводит"...