Algorytm Dijkstry

Question

Mam do rozwiązania poniższe zadnie z zastosowaniem algorytmu Dijkstry. Mam napisane trochę kodu niestety nie wiem jak wprowadzić ten algorytmu

Firma spedycyjna przyjmuje towary w centrali, skąd rozsyła do odbiorców w całym kraju.
Trasy między miastami są zapisane w pliku w następujący sposób:
<miasto> <miasto> <odległość>
Przykładowy plik:
Szczecin Poznan 220
Szczecin Koszalin 110
Poznan Bytom 300
Poznan Lodz 130
Lodz Katowice 170
Bytom Katowice 15
Bytom Wroclaw 180
W wyniki działania programu zostanie tworzony plik z trasami spedycyjnymi w następującej
postaci (przykład dla centrali w Poznaniu):
Poznan -> Bytom: 300
Poznan -> Lodz -> Katowice: 300
Poznan -> Szczecin -> Koszalin: 330
Poznan -> Lodz: 130
Poznan -> Szczecin: 220
Poznan -> Bytom -> Wroclaw: 480
Trasy spedycyjne mają najkrótsze możliwe długości. Należy wykorzystać algorytm Dijkstry.
Program uruchamiany jest z linii poleceń z potrzebnymi przełącznikami, natomiast
uruchomienie programu bez parametrów powoduje wypisanie krótkiej instrukcji.

 

#include <iostream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <fstream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <utility>

//#include "def.cpp"
//#include "funkcje.h"

using namespace std;
struct Node {
    string city;
    vector<pair<unsigned, unsigned>> connections;
};

int findOrAddCity(vector<Node>& g, const string& name)
{
    for (int i = 0; i < g.size(); i++)
        if (g[i].city == name) return i;

    g.push_back({ name, {} });
    return g.size() - 1;
}
int wczytaj_arg(int argc, char* argv[])
{
  
        int pozI = 0;
        int pozC = 0;
        string nPlikuI = "";
        string nPlikuC = "";
        string plik, centrala;
        if (argc == 5)
        {
            for (int i = 0; i < argc; i++) {
                if ((string(argv[i]) == "-i") and i < argc - 1) {
                    pozI = i + 1;
                    plik = argv[pozI];
                }
                if ((string(argv[i]) == "-c") and i < argc - 1) {
                    pozC = i + 1;
                    centrala = argv[pozC];
                }
            }
            cout << "\nNazwa pliku wejściowego : " << plik << endl;
            cout << "Nazwa Centrali: " << centrala << endl;

        }
        else
        {
            cout << "ZŁE ARGUMENTY\n" << "PODAJ : \n\n" << "-i nazwa pliku wejsciowego \n -c nazwa centrali\n";
        }
        return pozI;
    }

int main(int argc, char* argv[])
{
    
    fstream plik1;
    string linia;
	system("chcp 1250");
	system("cls");
	
	wczytaj_arg(argc, argv);
	string nazwa_pliku = argv[2];
	
    plik1.open(nazwa_pliku);
    if (plik1.good() == true)
    {
       
           
     
        while (!plik1.eof()) {
            getline(plik1, linia);
            istringstream ifs(linia);


            vector<Node> graph;
            string n1, n2;
            unsigned dist;

            while (ifs >> n1 >> n2 >> dist) {
                int i1 = findOrAddCity(graph, n1);
                int i2 = findOrAddCity(graph, n2);
                graph[i1].connections.push_back(make_pair(i2, dist));
            }


            for (auto& i : graph) {
                cout << i.city;

                for (auto& c : i.connections)
                    cout << graph[c.first].city << " - " << c.second << endl;
                
            }

        }
        cout << endl;
        plik1.close();

    }
    else cout << "\n\tBłąd otwarcia pliku";


}

 

Comments

https://eduinf.waw.pl/inf/alg/001_search/0138.php bierzesz ten o groszej złożoności czasowej i już masz wszystkie drogi wraz z kosztem

---

@wodzu_37, poprawiłem twojego maina, bo trochę bezsensów tam jest:

int main(int argc, char* argv[])
{
	system("chcp 1250");
	system("cls");

	wczytaj_arg(argc, argv);
	std::string nazwa_pliku = argv[2];

	std::ifstream ifs(nazwa_pliku);
	std::vector<Node> graph;
	std::string n1, n2;
	unsigned dist;

	while (ifs >> n1 >> n2 >> dist) {
		int i1 = findOrAddCity(graph, n1);
		int i2 = findOrAddCity(graph, n2);
		graph[i1].connections.push_back(std::make_pair(i2, dist));
	}

	for (auto& i : graph) {
		cout << i.city;
		for (auto& c : i.connections)
			std::cout << graph[c.first].city << " - " << c.second << '\n';
	}

	return 0;
}

 

---

Wkleiłem twój kod i jest coś takiego , jak to naprawić?

---

Pokaż zawartość plik.txt.

---

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

 

---

A co te minusy robią za nazwami miast startowych? Przecież nazwy Bytom i Bytom- są traktowane jak dwa różne miasta.

Popraw wyświetlanie na:

for (auto& i : graph) {
    std::cout << i.city << '\n';
    for (auto& c : i.connections)
        std::cout << '\t' << graph[c.first].city << " - " << c.second << '\n';
}

Nieco czytelniej będzie.