Demo entry 2327063

Algoritmo di Dijkstra

   

Submitted by anonymous on Jul 23, 2015 at 18:55
Language: C++. Code size: 1.4 kB.

#include <stdio.h>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

#define MAXN 100000

struct collegamento {
    int collegato;
    int peso;
};

// Funzione che definisce la priorità
bool compare(int first, int second) {
    return (dist[first]>dist[second]);
    
}

vector <collegamento> grafo[MAXN+1];
vector <int> prior;
int dist[MAXN+1];

int dijkstra(int start, int final) {
    // Inizializzo le strutture di dati
    dist[start]=0;
    prior.push_back(start);
    make_heap(prior.begin(),prior.end(),compare);
    
    while (prior.size()>0) {
        // Scelgo il vertice con priorità maggiore
        int attuale=prior.front();
        pop_heap(prior.begin(),prior.end(),compare);
        prior.pop_back();
        if(attuale==final) break; // Non proseguo se ho trovato ciò che mi interessa
        
        for (unsigned int i=0; i<grafo[attuale].size(); i++) {
            // Se trovo una soluzione migliore per un nodo, l'aggiungo alla priority queue
            if(dist[grafo[attuale][i].collegato]>dist[attuale]+grafo[attuale][i].peso || dist[grafo[attuale][i].collegato]==0){
                dist[grafo[attuale][i].collegato]=dist[attuale]+grafo[attuale][i].peso;
                prior.push_back(grafo[attuale][i].collegato);
                push_heap(prior.begin(),prior.end(),compare);
            }
        }
    }
    
    return dist[final];
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).