Meglio fatto da noi

Sull'algoritmo di Dijkstra, un po' intimiditi, pensavamo di trovarne uno già fatto in giro. Poi ci siamo accorti che di quelli disponibili in rete ciascuno aveva le sue pecche.

Dato che a sbagliare siamo bravissimi da noi, ecco a voi il succo delle nostre meningi:

// Dijkstra's Algorithm

#include <iostream.h>
#include <conio.h>
#include <stdio.h>
using namespace std;

#define INF 30000

// Definisce il numero dei nodi del grafo
const int LEVELS = 5;

typedef char luogo[20];

luogo places[LEVELS]= {"Bari", "Giovinazzo", "Bitonto", "Molfetta", "Terlizzi"};

int main() {

    // Definisce una matrice contenente le distanze tra due nodi
    // Gli elementi indicati con -1 indicano che non esiste un percorso diretto tra i due nodi

    int L[LEVELS][LEVELS] = {
                {-1, 21, 18, -1, -1},//Bari
                {21, -1,  9,  7, 16},//Giovinazzo
                {18,  9, -1, -1, 13},//Bitonto
                {-1,  7, -1, -1, 10},//Molfetta
                {-1, 16, 13, 10, -1},//Terlizzi
            };

    int potenziali[LEVELS];
    int definitivi[LEVELS];
    int path[LEVELS];
    int potfrom[LEVELS];
    int from;
    int to;
    int i;
    int current;
    int min;
    int posmin;
    int nuovopotenziale;
    int n;

    // Chiede punto di partenza e punto di arrivo
    do {
       printf ("Da dove vuoi partire?\n");
       for (i = 0; i < LEVELS; i++) {
           printf ("%d) %s\n", i+1, places[i]);
       }
       scanf ("%d", &from);
    } while ((from <= 0) || (from > LEVELS));
    from--;
    do {
       printf ("\nDove vuoi andare?\n");
       for (i = 0; i < LEVELS; i++) {
           if (i != from) {
              printf ("%d) %s\n", i+1, places[i]);
           }
       }
       scanf ("%d", &to);
       to--;
    } while ((from < 0) || (from >= LEVELS) || (from == to));
        
    // All'inizio i potenziali sono infiniti
    // e nessun nodo è definitivo
    for (i = 0; i < LEVELS; i++) {
        potenziali[i] = INF;
        potfrom[i] = INF;
        definitivi[i] = 0;
    }

    // Il nodo di partenza ha all'inizio potenziale 0
    // (ovvero dista zero da se stesso)
    // è anche definitivo
    potenziali[from] = 0;
    definitivi[from] = 1;
    current=from;
    do {
    // Cerco nodi adiacenti al nodo corrente
       for (i = 0; i < LEVELS; i++) {
           if (L[current][i] != -1) {
              if (definitivi[i] == 0) {
                 nuovopotenziale = L[current][i] + potenziali[current];
    // Aggiorno il potenziale solo se minore dell'attuale
                 if (nuovopotenziale < potenziali[i]) {
                    potenziali[i] = nuovopotenziale;
                    potfrom[i] = current;
                 }
              }
           }
       }
    // Cerco il nodo con potenziale minimo
       for (i=0; i < LEVELS; i++) {
           if (definitivi[i] == 0) {
              min = potenziali[i];
              posmin=i;
              break;
           }
       }
       for (i=i+1; i < LEVELS; i++) {
           if (definitivi[i] == 0) {
              if (potenziali[i] < min) {
                 min = potenziali[i];
                 posmin = i;
              }
           }
       }
    // Rendo definitivo il minimo
       definitivi[posmin] = 1;
       current = posmin;
        
    } while (current != to);
    
    // Visualizza risultati
    printf ("\nIl percorso minimo e' %d Km, facendo le seguenti tappe:\n", potenziali[to]);
    i = to;
    n = 0;
    do {
        path[n] = i;
        i = potfrom[i];
        n++;
    } while (i != INF);
    for (i=n-1; i>=0; i--) {
        printf ("%s\n", places[path[i]]);
    }
    getch();
}