Plik txt jako graf

Question

Cześć!

W jaki sposób mogę danie w pliku txt wyglądający w następujący sposób
<miasto>  <miasto> <odległość>
zapisać do grafu abym mógł wykorzystać metodę Dijkstra do znalezienia najkrótszej drogi między miastami

Comments

Nie wiesz, jak czytać z pliku, czy jak zaimplementować graf?

---

Jak zaimplementować jako graf

---

Jeśli to jest odpowiedź do mojego pytania w komentarzu, to powinieneś dać je także jako komentarz.

---

Tak to jest odpowiedź .

Jestem nowy na forum i się dopiero go uczę

---

No to pamiętaj, że dyskusje prowadzi się w komentarzach, bo jak coś napiszesz jako odpowiedź, to raz, że inni udzielający się w wątku nie dostają powiadomienia, a dwa - to sprzeczne z koncepcją tego typu for.

PS. możesz swoją odpowiedź przenieść do komentarzy.

Answer 1

Taki graf możesz zrealizować np. tak:

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <utility>


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


int findOrAddCity(std::vector<Node> &g, const std::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 main()
{
    std::istringstream ifs("A B 1 A C 3 B A 2 C A 666");
   
    
    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) {
        std::cout << i.city << '\n';
        for (auto &c : i.connections) 
            std::cout << '\t' << graph[c.first].city << " dist: " << c.second << '\n';
    }
}

Można by oczywiście użyć mapy, ale wydaje mi się, że prościej Ci będzie poruszać się po tablicy indeksami niż nazwami miast.

Comments

No i jeszcze unikalność (lub nie) drogi z A -> B. Ale masz rację. Dla prostoty przykładu nie ma co komplikować set'em czy mapą.