Visualizzazione dei risultati da 1 a 5 su 5

Discussione: [C++] Algoritmo di Dijkstra e determinazione cammino minimo

  1. #1
    Utente di HTML.it
    Registrato dal
    Apr 2017
    Messaggi
    21

    [C++] Algoritmo di Dijkstra e determinazione cammino minimo

    Salve, mi aiutate con questo codice? In pratica dati dei nodi, costruisco la matrice di adiacenza e poi dato un nodo di partenza e uno di arrivo mi serve trovare il costo del cammino minimo e il percorso..Ma non funziona correttamente..ecco il codice:
    codice:
    #include <iostream>
    #include <climits>
    using namespace std;
    int main()
    {
    int n,i,j,p;
    char g,s;
    cout<<"Quanti nodi? ";
    cin>>n;
    int matrice[n][n];
    for(i=0;i<n;i++)
    {
    for(j=0;j<n;j++)
    {
    if(i==j) matrice[i][j]=0;
    else
    {
    cout<<"Il nodo "<<i<<" e' collegato al nodo "<<j<<"?(s/n) ";
    cin>>g;
    
    if(g=='s' || g=='S')
    {
    cout<<"Inserisci peso: ";
    cin>>p;
    matrice[i][j]=p;
    }
    else if(g=='n' || g=='N')
    {
    matrice[i][j]=-1;
    }
    } 
    }
    }
    for(i=0;i<n;i++)
    {
    if(i==0) cout<<" ";
    cout<<i<<" ";
    }
    cout<<endl;
    for(i=0;i<n;i++)
    {
    for(j=0;j<n;j++)
    {
    if(j==0)
    {
    cout<<i<<" - | ";
    }
    if(matrice[i][j]==-1) cout<<"*| ";
    else
    {
    cout<<matrice[i][j]<<"| ";
    }
    }
    cout<<endl;
    }
    
    int D[n],Attuale,Min,Fine,Inizio; //vettore delle DISTANZE, variabile che contiene da dove si parte, percorso minimo, nodo di destinazione, nodo di partenza
    for (i=0; i<n; i++) D[i] = INT_MAX; 
    int P[n]; // vettore che contiene i nodi di precedenza
    for (i=0; i<n; i++) P[i] = -1;
    int V[n]; // vettore dei VISITATI che contiene, per ciascun nodo,
    // 0 se il nodo non è stato visitato, 1 altrimenti
    for (i=0; i<n; i++) V[i] = 0;
    cout<<"Inserisci nodo partenza: ";
    cin>>Inizio;
    cout<<"Inserisci nodo arrivo: ";
    cin>>Fine;
    D[Inizio] = 0;
    Attuale=Inizio;
    Min=0; // distanza minima dal nodo attuale
    while ( Attuale!=Fine && Min!=INT_MAX) {
    // si cerca il nodo più promettente, ossia quello con distanza minima
    // che non sia ancora stato visitato
    Min = INT_MAX;
    for (i=0; i<n; i++)
    if ( V[i] == 0 && D[i] < Min ){ Min = D[i]; Attuale = i; }
    V[Attuale] = 1; //Attuale è il nodo scelto che poi non si elaborerà più
    // aggiornamento vettori distanze (D) e provenienze (P)
    for (i=0; i<n; i++)
    if ( matrice[Attuale][i] != INT_MAX && D[i] > D[Attuale] + matrice[Attuale][i])
    { D[i] = D[Attuale] + matrice[Attuale][i]; P[i] = Attuale; }
    } 
    
    /* stampa */
    if ( V[Fine] == 0)
    cout<<"NON esiste cammino da nodo "<<Inizio<<" a "<<Fine;
    else { cout<<"cammino di peso "<<D[Fine];
    i=Fine;
    cout<<"\npercorso a ritroso ";
    while (i!=Inizio) { cout<<i<<" "; i=P[i]; }
    cout<<i<<" "; }
    return 0;
    
    
    
    }
    Ultima modifica di Negan; 13-05-2018 a 15:04

  2. #2
    Utente di HTML.it
    Registrato dal
    Nov 2012
    residenza
    matrix
    Messaggi
    55
    sistema l'indentazione del codice mettendolo tra [ code ] [ / code ] (togli gli spazi dentro le quadre)
    Ultima modifica di astolfo96; 13-05-2018 a 15:00

  3. #3
    Utente di HTML.it
    Registrato dal
    Apr 2017
    Messaggi
    21
    fatto

  4. #4
    Moderatore di Programmazione L'avatar di alka
    Registrato dal
    Oct 2001
    residenza
    Reggio Emilia
    Messaggi
    23,664
    Quote Originariamente inviata da Negan Visualizza il messaggio
    Ma non funziona correttamente.. [...]
    Ovvero cosa succede? Ottieni un errore? Un risultato sbagliato?
    Aggiungi qualche dettaglio.
    MARCO BREVEGLIERI
    Software and Web Developer, Teacher and Consultant

    Home | Blog | Delphi Podcast | Delphi Succinctly (e-book)

  5. #5
    Utente di HTML.it
    Registrato dal
    Apr 2017
    Messaggi
    21
    il "cammino di peso" risulta errato

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2018 vBulletin Solutions, Inc. All rights reserved.