Djikstra

//Autore: Daniele Calisti

//Programma per simulare l'algoritmo di Djikstra

#include <limits.h>         //Serve per gestire i numeri infiniti
#include <stdio.h>          //Serve per i/o
#include <bits/stdc++.h>    //Include tutte strutture dati e funzioni della stl
using namespace std;


// Funzione per trovare il vertice con distanza minima tra tutti gli altri vertici
int minDistanza(vector<int>& dist, vector<bool>& visitato,int V)
{
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++)
        if (visitato[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;

    return min_index;
}

void stampaSoluzione(vector<int>& dist,int V)
{
    printf("Vertice \t Distanza dalla sorgente\n");
    for (int i = 0; i < V; i++)
        printf("%d \t\t %d\n", i+1, dist[i]);
}


void dijkstra(vector<vector<int>>& mat, int src, int V)
{
    vector<int> dist(V,INT_MAX); // Includerà le distanze dal vertice al vertice sorgente

    vector<bool> visitato(V); // visitato[i] sarò true se ho visitato il vertice, false altrimenti


    //La distanza da un vertice al vertice stesso è 0
    dist[src] = 0;

    // In questo ciclo trovo il cammino minimo
    for (int count = 0; count < V - 1; count++) {
        // Prendo la distanza minima dei vertici che non ho visitato
        int u = minDistanza(dist, visitato,V);

        //Mi segno che l'ho visitato
        visitato[u] = true;

        //Aggiorno la distanza del vertice adiacente partendo dal vertice che ho preso
        for (int v = 0; v < V; v++)
            // Agggiorno la distanza solo se non ho visitato il vertice
            if (!visitato[v] && mat[u][v] && dist[u] != INT_MAX && dist[u] + mat[u][v] < dist[v])
                dist[v] = dist[u] + mat[u][v];
    }

    stampaSoluzione(dist,V);
}

vector<vector<int>> caricaMatrice(vector<vector<int>>& mat)
{
    cout<<"Inserisci la matrice di adiacenza \n";
    for(int i=0;i<mat.size();i++)
    {
        for(int j=0;j<mat[0].size();j++)
        {
            //Se è il vertice stesso non devo inserire niente perchè è 0
            if(i == j)
                continue;

            cout<<"Cella "<<i+1<<"-"<<j+1<<": ";
            cin>>mat[i][j];
        }
    }

    return mat;
}

int chiediVertici()
{
    int V;
    cout<<"Numero vertici del grafo: ";
    cin>>V;

    return V;
}

int chiediSorgente()
{
    int sorgente;
    cout<<"Inserisci il vertice che vuoi raggiungere: ";
    cin>>sorgente;

    return sorgente;
}
int main()
{
    int V,sorgente; //V --> vertici del grafo, sorgente --> nodo da raggiungere

    V = chiediVertici();

    vector<vector<int>> mat(V, vector<int>(V,0));

    mat = caricaMatrice(mat);       //Gestito il fatto che un vertice ha peso 0 sullo stesso vertice, quindi non serve inserirlo

    sorgente = chiediSorgente();
    sorgente--;

    dijkstra(mat, sorgente,V);

    return 0;
}