Algorytm Dijkstry

[Majster18]

W projekcie na studiach mam użyć algorytmu dijkstry w celu wyznaczenia możliwie najkrótszych tras pomiędzy miastami. 

Przykładowa dane wejściowe:

Szczecin Poznan 220
Szczecin Koszalin 110
Poznan Bytom 300
Poznan Lodz 130
Lodz Katowice 170
Bytom Katowice 15
Bytom Wroclaw 180

Przykładowy wynik programu:

Poznan -> Bytom: 300
Poznan -> Lodz -> Katowice: 300
Poznan -> Szczecin -> Koszalin: 330
Poznan -> Lodz: 130
Poznan -> Szczecin: 220
Poznan -> Bytom -> Wroclaw: 480

Spędziłem już nad tym sporo czasu, lecz nadal jestem w tym samym miejscu. Udało mi się napisać program którego wynikiem jest:

Poznan->Szczecin->Bytom->Lodz: 650
Poznan->Bytom->Lodz: 430
Poznan->Bytom->Lodz: 430
Poznan->Lodz: 130
Poznan
Poznan
Poznan
Poznan

Kod źródłowy programu:

#include <iostream>
#include <fstream>
#include <string>

using namespace std;
struct Node {
	int Distance;
	string City;
	string SecondCity;
	Node*left;
	Node*right;

};
struct Data {
	string FirstCity;
	string SecondCity;
	int Distance;
};
void addLeaf(Node* &Root, string City, int distance) {
	if (!Root) {
		Root = new Node;
		Root->left = nullptr;
		Root->right = nullptr;
		Root->Distance = distance;
		Root->City = City;
	}
	else if (distance < Root->Distance) {

		addLeaf(Root->right, City, distance);
	}
	else {

		addLeaf(Root->left, City, distance);
	}

}
void Print(Node* node, int indent)
{
	if (!node)
		return;
	Print(node->right, indent + 3);
	for (int i = 0; i < indent; ++i)
		cout << " ";
	cout << node->Distance << "\n";
	Print(node->left, indent + 3);
}

void Min(Node* root)
{
	if (root->right != nullptr) {
		root = root->right;
		Min(root);
	}
	else {
		cout << root->Distance;
	}

}
void Max(Node* root)
{
	if (root->left != nullptr) {
		root = root->left;
		Min(root);
	}
	else {
		cout << root->Distance;
	}

}
void RemoveTree(Node* &root)
{
	if (root == nullptr)
		return;
	RemoveTree(root->left);
	RemoveTree(root->right);
	delete root;
	root = nullptr;
}
void function(string IndirectCity) {



}
void Route(Node* root, int distance) {
	{


		if (root == nullptr) {
			return;
		}

		else {
			Route(root->right, distance);
			cout << "->" << root->City;
			Route(root->left, distance);
			distance += root->Distance;
		}
		if (root->left == nullptr) {
			cout << ": " << distance;
			distance = 0;
		}


	}
}

int main() {

	Node* Root = nullptr;
	Data tab[100];
	fstream InputFile;
	string StartCity = "Poznan";
	string IndirectCity = "Poznan";;
	int Counter = 0;
	InputFile.open("file.txt", ios::in);
	if (InputFile.good() == true) {
		string line;
		string FirstCity;
		string SecondCity;
		int Distance;
		int i = 0;


		do {
			InputFile >> FirstCity;
			InputFile >> SecondCity;
			InputFile >> Distance;
			tab[i].FirstCity = FirstCity;
			tab[i].SecondCity = SecondCity;
			tab[i].Distance = Distance;
			i++;
			Counter++;
		} while (getline(InputFile, line));

	}
	InputFile.close();
	int distance = 0;
	int temp = 0;
	for (int j = 0; j < Counter; j++) {

		for (int i = j; i < Counter; i++) {
			if (tab[i].FirstCity.compare(IndirectCity) == 0) {
				distance += tab[i].Distance;
				addLeaf(Root, tab[i].SecondCity, distance);
				StartCity = tab[i].SecondCity;
			}
			else if (tab[i].SecondCity.compare(IndirectCity) == 0) {
				distance += tab[i].Distance;
				addLeaf(Root, tab[i].FirstCity, distance);
				StartCity = tab[i].FirstCity;
			}

		}

		distance = 0;
		IndirectCity = "Poznan";
		StartCity = "Poznan";
		cout << StartCity;
		Route(Root, 0);
		RemoveTree(Root);
		cout << endl;
	}
	cout << endl;


	system("pause");
}
 

Niestety nie wiem co dalej z tym zrobić . Byłbym wdzięczny za jakąkolwiek pomoc

[Sopelek997]

Patrząc na kod nie wiem po co ci tutaj algorytm dijkstry skoro masz tutaj drzewo, a nie graf. W dodaku każdy węzeł tego drzewa może mieć maksymalnie dwoje dzieci. Wystarczy ze przejdziesz przez to drzewo wgłąb, lub wszerz (DFS, BFS) konstruując dla każdego dziecka odległość od początku (odległość od początku do rodzica + odległość od rodzica do dziecka), a następnie wypiszesz te odległości.

 

 

Inna jest sprawa, że ten kod nie ma nic wspólnego z treścią. Musisz mieć graf, a nie drzewo. Musisz zmienić strukturę danych.

[Majster18]

Niestety nie mogę zmienić struktury danych na graf. W poleceniu mam, abym użył drzewa bądź listy, więc wybrałem drzewo. 

[Sopelek997]

No to niestety nie da się tego zrobić, bo nawet w przykładzie to nie jest drzewo

http://screenshooter.net/100253651/ofnqtgr

[Majster18]

Dobra, znalazłem na necie działający algorytm, tylko że wprowadzane do niego dane wyglądają następująco:

int graph[V][V] = {
{ 0, 220, 110, 0, 0, 0, 0 },  //=>Szczecin
{ 220, 0, 0, 300, 130, 0, 0 }, //=>Poznan
{ 110, 0, 0, 0, 0, 0, 0 },     //=>Koszalin
{ 0, 300, 0, 0, 0, 15, 180 },  //=>Bytom
{ 0, 130, 0, 0, 0, 170, 0 },  //=>Lodz
{ 0, 0, 0, 15, 0, 0, 0 },//=>Katowice
{ 0, 0, 0, 0, 0, 0, 180 }//=>Wroclaw
};

A mój plik z danym wygląda tak:

Szczecin Poznan 220
Szczecin Koszalin 110
Poznan Bytom 300
Poznan Lodz 130
Lodz Katowice 170
Bytom Katowice 15
Bytom Wroclaw 180

Przykładowo linijka { 0, 220, 110, 0, 0, 0, 0 }, dotyczy Szczecina:

Szczecin->Szczecin = 0

Szczecin->Poznan = 220

Szczecin->Koszalin= 110

Szczecin->Bytom = 0

Szczecin->Lodz = 0

Szczecin->Katowice = 0

Szczecin->Wroclaw = 0

Niestety nie mam pomysłu jakby to zapisać  

 

 

[VereX.]

Dobra, znalazłem na necie działający algorytm, tylko że wprowadzane do niego dane wyglądają następująco:

int graph[V][V] = {
{ 0, 220, 110, 0, 0, 0, 0 },  //=>Szczecin
{ 220, 0, 0, 300, 130, 0, 0 }, //=>Poznan
{ 110, 0, 0, 0, 0, 0, 0 },     //=>Koszalin
{ 0, 300, 0, 0, 0, 15, 180 },  //=>Bytom
{ 0, 130, 0, 0, 0, 170, 0 },  //=>Lodz
{ 0, 0, 0, 15, 0, 0, 0 },//=>Katowice
{ 0, 0, 0, 0, 0, 0, 180 }//=>Wroclaw
};

A mój plik z danym wygląda tak:

Szczecin Poznan 220
Szczecin Koszalin 110
Poznan Bytom 300
Poznan Lodz 130
Lodz Katowice 170
Bytom Katowice 15
Bytom Wroclaw 180

Przykładowo linijka { 0, 220, 110, 0, 0, 0, 0 }, dotyczy Szczecina:

Szczecin->Szczecin = 0

Szczecin->Poznan = 220

Szczecin->Koszalin= 110

Szczecin->Bytom = 0

Szczecin->Lodz = 0

Szczecin->Katowice = 0

Szczecin->Wroclaw = 0

Niestety nie mam pomysłu jakby to zapisać  

To jest po prostu zwykła tablica, wczytaj dane potem je rozdziel i wpakuj do tablicy, domyślnie niech wszędzie będzie wartość 0.