Djikstra

#include <limits.h>
#include <stdio.h>
#include <bits/stdc++.h>
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, dist[i]);
}


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

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

    //Inizializzo le distanze a infinito e l'array a false per dire che non ho visitato nessuno
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, visitato[i] = false;

    //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);
}

int main()
{
    int V,sorgente;
    cout<<"Numero vertici del grafo: ";
    cin>>V;
    vector<vector<int>> mat(V, vector<int>(V,0));

    cout<<"Inserisci la matrice di adiacenza \n";
    for(int i=0;i<V;i++)
    {
        for(int j=0;j<V;j++)
        {
            cout<<"Cella "<<i+1<<"-"<<j+1<<": ";
            cin>>mat[i][j];
        }
    }

    cout<<"Inserisci il vertice che vuoi raggiungere: ";
    cin>>sorgente;

    dijkstra(mat, sorgente,V);

    return 0;
}