gistfile1.txt

#include <iostream>
#include <random>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <chrono>

using namespace std::chrono;
using std::cout;
using std::endl;

class Dynamic_Graph {
public:
    struct Edge {
        unsigned int connection_to;
        int weight;
        Edge(int weight, unsigned int connection_to) : connection_to(connection_to), weight(weight) {}
    };

    Dynamic_Graph(unsigned int n) : vertex_count(n) {
        edges.resize(n);
    }

    void addEdge(unsigned int from, unsigned int to, int weight) {
        edges[from].push_back(Edge(weight, to));
    }

    unsigned int get_vertex_count() const { return vertex_count; }
    const std::vector<Edge>& iter_edges(unsigned id) const { return edges[id]; }

    int weight_of(unsigned int from, unsigned int connected_to) {
        for (auto &edge : edges[from]) {
            if (edge.connection_to == connected_to) {
                return edge.weight;
            }
        }
        return -1;
    }

private:
    std::vector<std::vector<Edge>> edges;
    const unsigned int vertex_count;
};

void randomize_graph(Dynamic_Graph& G, int num_of_edges)
{
    srand(7);
    const unsigned int graph_size = G.get_vertex_count();
    const unsigned int iterations = num_of_edges;

    for (unsigned int i = 0; i < iterations; i++)
    {
        unsigned a = rand() % graph_size;
        unsigned b = rand() % graph_size;
        G.addEdge(a, b, rand() % 1000);
    }
}

struct result_props {
    int distance = 0;
    int last = -1;
};

void DjikstraAlgoritm(const Dynamic_Graph& graph, std::vector<result_props> &result, unsigned start) {
    for (size_t i = 0; i < graph.get_vertex_count(); i++)
        result[i].distance = 2000000;
    result[start].distance = 0;

    auto compare_paths = [&](unsigned p1, unsigned p2){ return result[p1].distance > result[p2].distance; };

    std::vector<unsigned> doSprawdzenia = { start };
    std::unordered_set<unsigned> sprawdzone;

    while (!doSprawdzenia.empty()) {
        //znajdz wierzcholek o najmniejszej wartosci dis (ver)

        auto ver = doSprawdzenia.back();
        doSprawdzenia.pop_back();

        sprawdzone.emplace(ver);

        for (auto edge : graph.iter_edges(ver))
        {
            if (sprawdzone.count(edge.connection_to) > 0)
                continue;

            auto existing = std::find(doSprawdzenia.begin(), doSprawdzenia.end(), edge.connection_to);
            if (existing != doSprawdzenia.end()) {
                // jeśli juz jest w priority queue, sprawdz czy ta krawedz jest lepsza.
                // Jesli tak, to zmieniamy priorytet (przez usunięcie i ponowne dodanie).
                // Jesli nie, to ignorujemy i szukamy dalej.
                if (result[edge.connection_to].distance > result[ver].distance + edge.weight) {
                    doSprawdzenia.erase(existing);
                } else {
                    continue;
                }
            }

            result[edge.connection_to].distance = result[ver].distance + edge.weight;
            result[edge.connection_to].last = ver;
            doSprawdzenia.insert(
                std::lower_bound(doSprawdzenia.begin(), doSprawdzenia.end(), edge.connection_to, compare_paths),
                edge.connection_to
            );
        }
    }
}

int main()
{
    //Losowy graf z 40000 wierzcholkami i 300000 krawedziami
    Dynamic_Graph graph(40000);

    graph.addEdge(0, 7, 1);//a->h
    graph.addEdge(0, 4, 1);//a->e

    graph.addEdge(1, 2, 2);//b->c

    graph.addEdge(3, 0, 4);//d->a
    graph.addEdge(3, 7, 1);//d->h

    graph.addEdge(4, 5, 3);//e->f

    graph.addEdge(5, 6, 7);//f->g
    graph.addEdge(5, 8, 1);//f->i
    graph.addEdge(5, 1, 1);//f->b
    graph.addEdge(5, 2, 3);//f->c

    graph.addEdge(7, 8, 9);//h->i

    graph.addEdge(8, 9, 2);//i->j

    graph.addEdge(9, 6, 1);//j->g
    
    randomize_graph(graph, 300000); 
    
    auto vertex1 = 5;
    auto vertex2 = 4;

    cout << "Weight: " << graph.weight_of(vertex2, vertex1) << endl;
    cout << "from:" << vertex2 << endl;
    cout << "to: " << vertex1 << endl;

    cout << endl;

    cout << "All edges from " << vertex1 << endl;
    for (auto i : graph.iter_edges(vertex1))
    {
        cout << i.weight << endl;
    }

    std::vector<result_props> result(graph.get_vertex_count());

    DjikstraAlgoritm(graph, result, 3);

    cout << "Shortest path form 3 to: " << endl;
    for (size_t i = 0; i < graph.get_vertex_count(); i++)
    {
        if (result[i].distance == 2000000) {
            continue;
        }
        cout << i << " " << result[i].distance << "\t";
        if (i != 3) {
            int id = result[i].last;
            while (id != 3) {
                cout << id << " ";
                id = result[id].last;
            }
        }
        cout << endl;
    }
}