wxWidgets
Algoritmo di Dijkstra
In questa sezione si userà il componente wxGrid, disponibile nella cartella Container di wxDev-C++, per rappresentare la matrice delle adiacenze.
Avviare un nuovo progetto wxDev-C++, basato su wxWidgets Frame, salvarlo con nome Dijkstra
Preparare la seguente interfaccia utente, secondo le indicazioni fornite di seguito.
Aggiungere al form:
un wxSizer con proprietà Orientation=wxVertical;
un wxFlexGridSizer con proprietà Rows=3;
un wxStaticText con proprietà Label="Numero di Nodi:"
un wxEdit con proprietà Text=0;
un wxStaticText con proprietà Label="Nodo di Partenza"
un wxEdit con proprietà Text=0;
un wxStaticText con proprietà Label="Nodo di arrivo"
un wxEdit con proprietà Text=0;
un wxStaticText con proprietà Label="Matrice delle adiacenze" e proprietà Allineamento=wxALIGN_LEFT;
un wxGrid con proprietà RowCount=10 e proprietà Column Count=10;
un wxButton con proprietà Label="Calcola";
un wxMemo Con proprietà Strings="Cammino di costo minimo".
Algoritmo di Dijkstra.
Ricerca del cammino minimo dal nodo i al nodo j su un grafo pesato (con pesi≥0).
Il grafo è rappresentato tramite la matrice delle adiacenze e i nodi sono indicati con un numero intero da 0 a n-1.
Strutture dati
n: numero dei nodi che compongono il grafo.
matrice delle adiacenze g. È una matrice di nxn interi
vettore delle distanze. È un vettore di n interi. Per ciascun nodo contiene la minima distanza dal nodo di partenza. Ad ogni elemento viene assegnato il valore iniziale INT_MAX, per indicare che il nodo non è ancora stato raggiunto da nessun possibile percorso
vettore delle provenienze. È un vettore di n interi. Per ciascun nodo contiene il numero del nodo che lo precede nel cammino minimo. Ad ogni elemento viene assegnato il valore iniziale -1, per significare che non è stato ancora raggiunto da un possibile percorso.
vettore dei nodi visitati. È un vettore di n booleani (o interi). Ad ogni elemento viene assegnato il valore iniziale 0 (Falso, non visitato), successivamente, assumerà il valore 1 (Vero, visitato) quando verrà preso in considerazione per stabilire se appartiene ad un persorso di costo minimo.
Variabili intere
i e j indice di riga e indice di colonna per la matrice delle adiacenze.
nodoAttuale. È una variabile intera che indica il nodo in esame. Come valore iniziale le viene assegnato il numero del nodo di partenza.
inizio è il numero del nodo di partenza, fine è il numero del nodo di arrivo. Sono due variabili intere il cui valore viene fornito in input.
minDistanza è un itero usato per cercare la distanza minima dopo aver esaminato tutti i costi dei percorsi per raggiungere un nodo successore.
Algoritmo
nodoAttuale ← inizio
visitato[nodoAttuale] ← 1
distanza[inizio] ← 0
minDistanza = 0
finchè (nodoAttuale diverso da fine) e (ci sono ancora nodi raggiungibili)
per tutti i nodi j
Aggiungi al costo del cammino percorso, il costo tra il nodoAttuale e il nodo j
se il costo ottenuto è minore del costo per raggiungere i
sostituisci il costo (distanza[j]) con il costo tra ila nodoAttuale e il percorso verso j
aggiorna il nodo di provenienza
Scelta del nodo a cui si è giunti con un percorso di costo minimo nodo e che non sia ancora stato visitato
(questo diventa nodoAttuale).
il nodo scelto diventa nodoAttuale. Non dovrà essere riesaminato, quindi lo si marca come visitato
fine finchè
Programma
Alla fine della funzione CreateGUIControls, contenuta nel file Dijkstra.cpp, aggiungere le seguenti righe:
Layout(); GetSizer()->Fit(this); GetSizer()->SetSizeHints(this); Center(); ////GUI Items Creation End // la griglia viene riempita di simboli ∞ // si assume che tra i due nodi non via un percorso // sulla diagonale principale vengono inseriti 0 // per indicare che il nodo di partenza e il nodo di arrivo coincidono for (int i=0; i<10; i++) for (int j=0; j<10; j++) { WxGrid1->SetCellAlignment(i, j, wxALIGN_CENTER, wxALIGN_CENTER); if (i==j) WxGrid1->SetCellValue(i, j, _("0")); else WxGrid1->SetCellValue(i, j, _("oo")); } // l'intestazione di riga viene sostituita // con il nome del nodo di partenza wxString msg; for (int i=0; i<10; i++) { msg.Printf(_("nodo %d"), i); WxGrid1->SetRowLabelValue(i, msg); } // l'intestazione di colonna viene sostituita // con il nome del nodo di arrivo for (int i=0; i<10; i++) { msg.Printf(_("nodo %d"), i); WxGrid1->SetColLabelValue(i, msg); } } void DijkstraFrm::OnClose(wxCloseEvent& event) { Destroy(); }
Immissione dei dati iniziali
Nelle caselle di testo dovranno essere specificati il numero dei nodi del grafo, il numero del nodo di partenza e il numero del nodo di arrivo. Nella griglia bisognerà scrivere la matrice delle adiacenze, sostituendo i valori ∞ già presenti con i costi dei collegamenti tra il nodo della riga e il nodo della colonna. I risultati verranno mostrati nel componente wxMemo.
Dopo aver inserito i valori nelle caselle di testo e aver completato la matrice delle adiacenze, si può procedere alla ricerca del cammino di costo minimo tra il nodo di partenza e il nodo di arrivo specificati
Nel gestore dell'evento onClick del pulsante Calcola aggiungere le seguenti righe:
I nodi sono numerati a partire da zero allo scopo di metterli in corrispondenza con gli indici dei vettori
void DijkstraFrm::WxButton1Click(wxCommandEvent& event) { // insert your code here int n, inizio, fine; int i, j, k; wxString msg; // i valori nelle caselle di testo vengono // convertiti in intero e assegnati alle variabili n = wxAtoi(WxEdit1->GetValue()); inizio = wxAtoi(WxEdit2->GetValue()); fine = wxAtoi(WxEdit3->GetValue()); // la sezione di griglia relativa alla matrice delle adiacenze // viene evidenziata in giallo. for (i=0; i<n; i++) for (j=0; j<n; j++){ WxGrid1->SetCellBackgroundColour(i, j, *wxYELLOW); WxGrid1->ForceRefresh(); } // nella casella wxMemo viene scritto il percorso da individuare msg.Printf(_("\ndal nodo %d al nodo %d"), inizio, fine); WxMemo1->AppendText(msg);
Dichiarazione della matrice delle adiacenze:
La dichiarazione int **g si legge: g è un puntatore ad un puntatore a intero che è l'equivalente di int *g[] g è un array di puntatori a interi, infatti, in un'espressione, un nome di array è usato senza le parentesi quadre viene trattato come il puntatore all'array.
int **g, costo;
// assegna a g l'indirizzo di un array di n puntatori a int
g = new int *[n];
// ogni elemento dell'array punta ad un array di interi
// ottenendo, quindi, una matrice di interi.
for (k=0; k<n; k++)
g[k] = new int[n];
// ad ogni elemento della matrice viene
// assegnato il corrispondente valore
// presente nella griglia
for (i=0; i<n; i++)
for (j=0; j<n; j++) {
msg = WxGrid1->GetCellValue(i, j);
if (msg.IsSameAs(_("oo")))
g[i][j] = INT_MAX;
else
g[i][j] = wxAtoi(msg);
}
Al costo infinito tra nodi b>i e j, non collegati direttamente, viene assegnato il valore predefinito INT_MAX.
Dichiarare i vettori:
distanze è un puntatore a int creare un array di n int ed assegnare il suo indirizzo a distanze provenienze è un puntatore a int creare un array di n int ed assegnare il suo indirizzo a provenienze visitato è un puntatore a int creare un array di n int ed assegnare il suo indirizzo a visitato
Che corrisponde alle seguenti dichiarazioni, seguite dalle relative inizializzazioni:
int *distanze, *provenienze, *visitato;
distanze = new int[n];
provenienze = new int[n];
visitato = new int[n];
Assegnare i valori iniziali agli elementi dei vettori.
Un elemento j del vettore distanze è associato ad un nodo j, questo elemento rappresenta la minima distanza del nodo j dal nodo di partenza.
for (i=0; i<n; i++)
distanze[i] = INT_MAX;
L'assegnazione del valore INT_MAX ad un nodo serve per specficare che il nodo non risulta ancora adiacente a nessuno dei nodi visitati.
Un elemento j del vettore provenienze specifica qual è il nodo precedente lungo il cammino di costo minimo. Il valore iniziale di ogni elemento dell'array è -1 per indicare che il nodo non è stato ancora raggiunto.
for (i=0; i<n; i++)
provenienze[i] = -1;
L'array visitato è un vettore di booleani. Per ciascun nodo specifica 0 se non visitato, 1 se visitato
for (i=0; i<n; i++)
visitato[i] = 0;
Il cammino inizia dal nodo inizio e il costo di questo primo passo è 0.
int nodoAttuale, minDistanza;
nodoAttuale = inizio;
distanze[inizio] = minDistanza = 0; // anche il costo del cammino è 0
Tra tutti i successori del nodoAttuale si cerca quello non ancora visitato ed avente il minimo costo:
while (nodoAttuale != fine && minDistanza != INT_MAX) {
minDistanza = INT_MAX;
for (j=0; j<n; j++)
if (!visitato[j] && distanze[j] < minDistanza) {
minDistanza = distanze[j];
nodoAttuale = j;
}
A questo punto si è trovato il nodo a cui si giunge con il minimo costo. Viene scelto per proseguire il cammino.
Il nodo scelto viene marcato come visitato per non essere più considerato
visitato[nodoAttuale] = 1;
valutazione dei costi tra tutti i successori del nodo attuale e aggiornamento dei costi dei cammini:
for (j=0; j<n; j++)
if (g[nodoAttuale][j] != INT_MAX
&&
distanze[j] > distanze[nodoAttuale] + g[nodoAttuale][j]
) {
distanze[j] = distanze[nodoAttuale] + g[nodoAttuale][j];
provenienze[j] = nodoAttuale;
}
}
stampa dei risultati:
if (!visitato[fine]){
msg.Printf(_("\nnon esiste cammino da nodo %d a &d"), inizio, fine);
WxMemo1->AppendText(msg);
} else {
msg.Printf(_("\ncammino di costo %d"), distanze[fine]);
WxMemo1->AppendText(msg);
i = fine;
WxMemo1->AppendText(_("\npercorso a ritroso: "));
while (i != inizio) {
msg.Printf(_("%d "), i);
WxMemo1->AppendText(msg);
i = provenienze[i];
}
msg.Printf(_("%d "), i);
WxMemo1->AppendText(msg);
}
Problemi:
Modificare i costi e verificare che viene scelto il percorso di costo minimo.
introdurre la matrice delle adiacenze di un grafo più complesso
Associare un nome ad ogni numero di nodo e stampare il percorso di costo minimo specificando i nomi anzichè i numeri dei nodi.