Mam problem z algorytmem Dijkstry nie mam już pomysłów jak mogę go zaimplementować w mój kod. Walczę z tym już ponad tydzień i nic nie idzie po mojej myśli. Mam już stworzoną listę sąsiedztwa tylko nie wiem co z nią dalej zrobić żeby działało to poprawnie kod w algorytmie jest trochę dziurawy ponieważ cały czas go zmieniam. Kończą mi się już pomysły jak powinienem to zrobić. Domyślam się że w kodzie będzie dużo błędów.
dane muszą być wpisane z pliku który wygląda następująco
Szczecin Poznan 220
Szczecin Koszalin 110
Poznan Bytom 300
Poznan Lodz 130
Lodz Katowice 170
Bytom Katowice 15
Bytom Wroclaw 180
algorytm ma podać najkrótszą trasę z wybranego przez użytkownika miasta do każdego możliwego
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
const int MAX_N = 100;
const int INF = 2147483647;
int x = 0;
string m[10];
struct miasto {
int numer_miasta;
miasto* nastepne;
struct sasiad* head;
};
struct sasiad {
miasto* wsk_miasto;
int odleglosc;
sasiad* następny;
};
struct kurwa {
int node;
int odl;
struct kurwa* next;
};
miasto* AddSearch(string& nazwa_miasta, miasto*& wsk_miasto) {
if (!wsk_miasto)
{
wsk_miasto = new miasto{ x,nullptr };
m[x] = nazwa_miasta;
x++;
return wsk_miasto;
}
if (m[wsk_miasto->numer_miasta] == nazwa_miasta)
return wsk_miasto;
if (nazwa_miasta != m[wsk_miasto->numer_miasta]) {
return AddSearch(nazwa_miasta, wsk_miasto->nastepne);
}
}
void dodaj_Sas(struct miasto* pomoc, miasto* m1, miasto* m2, int odl) {
struct miasto* pom = pomoc;
struct sasiad* nowy = new struct sasiad();
while (pom->numer_miasta != m1->numer_miasta)pom = pom->nastepne;
nowy->wsk_miasto = m2;
nowy->odleglosc = odl;
nowy->następny = pom->head;
pom->head = nowy;
}
void Print(miasto* wsk_miasto)
{
if (wsk_miasto != nullptr)
{
Print(wsk_miasto->nastepne);
cout << wsk_miasto->numer_miasta << endl;
}
}
void pisz_liste_miast(struct miasto* st)
{
struct miasto* pom = st;
struct sasiad* pom1;
while (pom != NULL)
{
cout << m[pom->numer_miasta] << ":";
pom1 = pom->head;
while (pom1 != NULL)
{
cout << pom1->wsk_miasto->numer_miasta << " " << pom1->odleglosc << ", ";
pom1 = pom1->następny;
}
cout << endl;
pom = pom->nastepne;
}
}
void klonuj_liste(struct miasto* m) {
miasto* head = nullptr;
}
void dijkstry(struct miasto* m, int numer_miasta_start, int x) {
int i, j, huj;
int d[MAX_N + 1], p[MAX_N + 1];
bool QS[MAX_N + 1];
struct miasto* L = nullptr;
struct sasiad* pw = nullptr;
for (int i = 0; i <= MAX_N; i++)
{
d[i] = INF; // koszty dojścia
p[i] = 0; // poprzednik na ścieżce
QS[i] = false; // przynależność do Q (false) lub S (true)
}
struct miasto* pom = m;
struct sasiad* pom1;
while (pom != nullptr) {
if (!L) {
L = new miasto;
L->numer_miasta = pom->numer_miasta;
L->head = pom->head;
L->nastepne = pom->nastepne;
}
if (L) {
L = new miasto;
L->numer_miasta = pom->numer_miasta;
L->head = pom->head;
L->nastepne = pom->nastepne;
}
pom1 = pom->head;
pw = L->head;
while (pom1 != nullptr) {
if (!pw) {
pw = new sasiad;
pw->odleglosc = pom1->odleglosc;
pw->wsk_miasto = pom1->wsk_miasto;
pw->następny = pom1->następny;
}
if (pom1->odleglosc < pw->odleglosc) {
pw->następny = pw;
pw = new sasiad;
pw->odleglosc = pom1->odleglosc;
pw->wsk_miasto = pom1->wsk_miasto;
pw->następny = pw->następny;
}
else {
pw = new sasiad;
pw->odleglosc = pom1->odleglosc;
pw->wsk_miasto = pom1->wsk_miasto;
pw->następny = pom1->następny;
}
pom1 = pom1->następny;
}
pom = pom->nastepne;
}
}
bool odczytaj_argumenty(int ile, char** argumenty, string& szInput, string& szOutput)
{
const string ETYKIETA_INPUT("-i");
const string ETYKIETA_OUTPUT("-o");
const int FLAGA_INPUT = 1;
const int FLAGA_OUTPUT = FLAGA_INPUT << 1;
const int POPRAWNY_WYNIK = FLAGA_INPUT | FLAGA_OUTPUT;
int wynik = 0;
for (int i = 1; i < ile - 1; i++)
{
string arg(argumenty[i]);
if (arg == ETYKIETA_INPUT)
{
szInput = argumenty[i + 1];
wynik |= FLAGA_INPUT;
}
if (arg == ETYKIETA_OUTPUT)
{
szOutput = argumenty[i + 1];
wynik |= FLAGA_OUTPUT;
}
}
if (wynik == POPRAWNY_WYNIK)
return true;
else
return false;
}
int main() {
ifstream file;
string m1, m2, miasto_wpisane = "Wroclaw";
int odleglosc, numer_miasta;
file.open("trasy.txt");
int i = 0, num = 0;
if (!file.is_open())
{
cout << "error" << endl;
cin >> i;
return 1;
}
miasto* head = nullptr;
miasto* klon = nullptr;
while (file >> m1 >> m2 >> odleglosc)
{
dodaj_Sas(head, AddSearch(m1, head), AddSearch(m2, head), odleglosc);
}
for (int i = 0; i < x; i++) {
cout << m[i] << endl;
}
for (num; miasto_wpisane != m[num]; num++) {
}
cout << num;
dijkstry(head, num, x);
pisz_liste_miast(head);
cout << endl;
return 0;
}