Algoritmo di Dijkstra

Algoritmi
1

sto provando a implementare l’algoritmo di dijkstra, ma non ci riesco: ho capito l’idea che c’è dietro ma non riesco ad applicarla, e i codici che ho cercato in rete sono sempre poco chiari. Qualcuno potrebbe darmi una mano, magari passandomi il suo codice?

2 
#include<bits/stdc++.h>
using namespace std;
const int oo = numeric_limits<int>::max();

typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vii> mii;

struct step{ //step dell'algoritmo
    int curr, //nodo corrente
        dist; //distanza da source

    step(){}
    step(int c, int d)
    : curr(c), dist(d) {}

    bool operator<(const step& s) //operator< per la coda di priorità
    const { return dist>s.dist; }
};

int v, e;
mii adj;

int dijkstra(mii& graph, int source, int target)
{
    vector<int> distance(graph.size(),oo); //distanze da source
    priority_queue<step> pq; //coda di priorità
    step head;
    pq.push({source,0}); //inserisco il primo step

    while(!pq.empty()){
        head = pq.top(); //prendo lo step alla distanza minore
        pq.pop();

        if(distance[head.curr]==oo){ //se non ho già chiuso questo nodo
            distance[head.curr]=head.dist; //aggiorno la distanza

            if(head.curr==target) return head.dist; //se è il mio target termino

            for(auto x : graph[head.curr]) //per ogni nodo adiacente
                if(distance[x.first]>head.dist+x.second) //se per raggiungerlo migliorerò il risultato
                    pq.push({x.first,head.dist+x.second}); //lo aggiungo alla coda
        }
    }

    return distance[target];
}

int main()
{
	ifstream in("input.txt");
	ofstream out("output.txt");

    in >> v >> e;
    adj.resize(v+1);
    for(int x=0, i, j, w; x<e; ++x){
        in >> i >> j >> w;
        adj[i].push_back({j,w}); // i->j di peso w
        adj[j].push_back({i,w}); // j->i di peso w
    }

    out << dijkstra(adj,1,v) << "\n";

	return 0;
}

Questo è essenzialmente il mio codice, non credo sia il migliore in assoluto ma fa bene il suo lavoro.
Ovviamente Dijkstra prevede anche l’assegnamento di un etichetta con il nodo padre ma solitamente nei problemi viene sempre chiesto solo il percorso minimo; in ogni caso credo tu sappia già come modificare il codice per fare anche quello! :smile:

3

Grazie mille! :slight_smile:
c’è un unica cosa che non ho capito:
for(auto x : graph[head.curr])
mi da errore,suppongo che sia un comando di c++11, qual è il suo corrispondente in c++?
EDIT: ah no ho capito, è un semplice for in cui a x si assegna direttamente il graph[head.curr][x]

4

Nel booklet delle ultime territoriali c’è un’implementazione di Dijkstra (task footing). È leggermente riadattata per il task, però ti basta ignorare del tutto l’if alle righe 43-46 e hai la versione “pulita” :smile:. Volendo puoi anche modificare il return finale in modo che venga restituito il vettore distanza (devi cambiare anche il tipo di ritorno della funzione da unsigned a std::vector<unsigned> e rimuovere il parametro arrivo) se hai bisogno di tutte le distanze.

1 Mi Piace