La complessità del tempo dell'algoritmo di Dijkstra
Considera le seguenti città: A, B, C, D, E e F collegate da strade:
Queste città sono collegate da strade (che si possono presumere essere dritte). La lunghezza della strada dalla città A alla città B è 4 unità; non è attratto per la scala. La lunghezza della strada dalla città A alla città C è di 5 unità; non è attratto per la scala. La lunghezza dalla città B alla città E è di 11 unità, non disegnata in scala. Le strade tra le altre città sono allo stesso modo indicate.
Le città: A, B, C, D, E e F sono i vertici di un grafico. Le strade sono i bordi del grafico. Tuttavia, questo grafico sarà rappresentato in una struttura di dati matematici, in modo diverso dal suo layout geografico.
L'algoritmo di Dijkstra può essere usato per trovare il percorso più breve tra un vertice di origine (diciamo a) e qualsiasi altro vertice. Per ulteriore semplicità, questo articolo mirerà a cercare il percorso più breve da A a E.
Esistono percorsi diversi da A a E, con lunghezze diverse, come segue:
A-B-D-F: 4 + 9 + 2 = 15A-B-E-F: 4 + 7 + 6 = 17
A-B-C-E-F: 4 + 11 + 3 + 6 = 24
A-B-C-E-D-F: 4 + 11 + 3 + 13 + 2 = 33
A-B-D-E-F: 4 + 9 + 13 + 6 = 32
A-B-E-D-F: 4 + 7 + 13 + 2 = 26
A-C-E-F: 5 + 3 + 6 = 14
A-C-B-D-F: 5 + 11 + 9 + 2 = 27
A-C-B-E-F: 5 + 11 + 7 + 6 = 29
A-C-B-E-F: 5 + 11 + 7 + 6 = 29
A-C-E-D-F: 5 + 3 + 13 + 2 = 14
A-C-B-E-D-F: 5 + 11 + 7 + 13 + 2 = 38
Da questo elenco, il percorso più breve è A-C-E-F, con una lunghezza totale di 14 unità.
L'obiettivo principale di questo articolo è trovare il tempo di esecuzione che l'algoritmo di Dijkstra prende per ottenere il percorso più breve da a a e. Il tempo non sarà dato in secondi o minuti. È il tempo di esecuzione totale relativo, chiamato complessità temporale, che verrà dato. È fornita anche la codifica C ++.
Grafico da usare
La complessità del tempo (tempo di esecuzione relativo) dipende principalmente dal tipo di grafico matematico utilizzato per rappresentare il layout geografico. Dipende anche dall'algoritmo (un altro tipo di algoritmo) usato per ordinare i vertici vicini di ogni vertice nell'algoritmo complessivo (algoritmo di Dijkstra). L'ordinamento dei vertici vicini non è affrontato in questo articolo.
Il grafico matematico scelto per questo articolo si chiama Matrix adiacenza. È:
Le intestazioni di fila sono i nomi della città da a a f. Le intestazioni della colonna sono gli stessi nomi di città da a a f. Ogni voce è la lunghezza di una strada da una città all'altra. La lunghezza di una strada da una città a se stessa è zero. La lunghezza di una strada da una città all'altra, dopo aver saltato una o più città, è anche zero. Vengono considerate solo strade dirette. Ogni voce si trova, prima per riga e poi per colonna. Ancora una volta, ogni voce è la lunghezza di una strada, senza saltare una città e non nella città stessa. Questa matrice è una rappresentazione matematica della rete geografica sopra indicata.
Quindi, la matrice è costituita da bordi, con le intestazioni di riga e colonna degli stessi vertici. La matrice è la struttura principale necessaria nel programma. Altri due vettori (array) sono utilizzati in questo programma di base.
L'algoritmo di Dijkstra
L'algoritmo di Dijkstra cerca il percorso più breve tra due vertici in un grafico (rete). La matrice sopra è il grafico, che corrisponde alla rete geografica sopra. Per semplicità, il programma in questo articolo cercherà il percorso più breve tra un vertice di origine e un vertice di destinazione. Proprio, il programma cercherà il percorso più breve dal vertice di origine, a, al vertice di destinazione, f.
L'algoritmo, rilevante per questo compito, è il seguente:
- Tutti i vertici sono contrassegnati come non visitati. A questo punto, vengono creati un insieme di tutti i vertici non visitati.
- Assegnare un valore di lunghezza del percorso provvisorio a tutti i vertici: la lunghezza del percorso dalla sorgente all'origine viene assegnato un valore zero; La lunghezza del percorso dalla sorgente a qualsiasi altro vertice viene assegnato il valore di infinito, i.e., un valore superiore al percorso più alto possibile, nel grafico. Il valore di ogni vertice verrebbe modificato almeno una volta, da un valore elevato a un valore inferiore, mentre l'algoritmo continua. Vertici possibili per il percorso più breve saranno focalizzati, a partire dal vertice di origine (a). Il vertice con il focus è chiamato vertice corrente. L'attuale vertice ha i vicini, meglio visualizzati dalla rete reale (layout geografico) sopra.
- C'è il vertice corrente e c'è il vertice visitato. In effetti, ci sarebbe più di un vertice visitato in una catena mentre l'algoritmo continua. Tutti i vertici precedenti considerati visitati sono nel percorso completo più breve che si sta sviluppando, a partire dalla fonte. La lunghezza del percorso dell'ultimo vertice visitato è nota (dovrebbe essere nota). Viene dichiarato un vertice visitato quando viene confermata la lunghezza del percorso. Il vertice visitato dà la lunghezza del percorso minima dalla fonte finora, poiché l'algoritmo è in corso. I vicini non visitati dell'attuale vertice, tranne il suo prossimo vicino visitato immediato, hanno valori provvisorie (lunghezze del percorso dalla sorgente), alcuni dei quali possono essere ancora infiniti (valore molto alto). Per ogni vicino non visitato e il vertice corrente, viene calcolata una nuova lunghezza del percorso provvisorio come segue: la lunghezza del percorso del vertice precedente vicino non visitato. Se questo risultato è inferiore a quello che c'era, poiché la lunghezza del percorso provvisorio dalla sorgente al vicino non visitato del vertice corrente, questo valore calcolato diventa il nuovo valore provvisorio per il vicino del vertice corrente. Cioè, il nuovo valore del percorso provvisorio per un vertice non visitato viene calcolato attraverso il vertice corrente dal vertice precedentemente visitato.
- Ci possono essere più di un vertico corrente. Quando tutti i vicini di ciascun vertice corrente sono stati accessibili e somministrati nuove lunghezze di percorso provvisorio appropriate, viene considerato il vertice corrente con la lunghezza del percorso minima dalla sorgente (minimo valore). Dal momento che aveva il minimo valore, il suo valore minimo è confermato come la lunghezza più breve del percorso finora. Il vertice precedentemente visitato viene rimosso dal set vertice non visitato. Un vertice visitato non verrà mai più controllato. Qualsiasi visita dopo avrebbe una lunghezza del percorso maggiore.
- I due passaggi precedenti vengono ripetuti, in ordine, per qualsiasi vertice corrente successivo che diventa un vertice visitato. Questa ripetizione continua fino al raggiungimento del vertice di destinazione. Il vertice di destinazione può essere qualsiasi vertice dopo il vertice di origine. Tuttavia, per semplicità, l'ultimo vertice, F della rete sopra, è stato scelto come vertice di destinazione per questo articolo.
- Man mano che l'algoritmo avanza, ogni genitore (precedentemente visitato) vertice e ogni bambino (successivo visitato) vertice, del percorso più corto dovrebbe essere registrato nel caso in cui il percorso più breve, per vertici, nonché il percorso più breve per lunghezza ha chiesto per). Quando il vertice di destinazione viene raggiunto e visitato, il percorso più corto completo può essere rintracciato all'indietro se è necessario il percorso per i vertici. Per quanto riguarda la lunghezza del percorso, è stato calcolato quando l'algoritmo progrediva.
Ilritmo di illustrazione di Dijkstra
La strada sopra
La rete viene utilizzata per illustrare l'algoritmo di Dijkstra. È ri-estagliato di seguito per un facile riferimento.
Inizia alla fonte, "A" con una lunghezza del percorso di zero. "A" è considerato visitato e rimosso dall'elenco non visitato (set). "A" viene inviato a un elenco visitato nel caso in cui sarà richiesto il percorso dai vertici.
Le lunghezze del percorso da A a B sono:
A-B = 4A-c-b = 5 + 11 = 16
Tra 4, 16 e infinito (che era lì), 4 è il minimo. Quindi, a B viene dato il valore provvisorio di 4 come lunghezza del percorso.
Le lunghezze del percorso da A a C sono:
A-c = 5A-B-C = 4 + 11 = 15
Tra 5, 15 e infinito (che era lì), 5 è il minimo. Quindi, a C viene dato il valore provvisorio di 5 come lunghezza del percorso.
B e C erano i vicini non visitati di A. Attualmente, ognuno ha una lunghezza del percorso provvisorio. Tra B e C, deve essere scelto un vertice contribuire al percorso complessivo finale. B e c hanno anche vicini.
I vicini non visitati di B sono D, E e C, con lunghezze infinite provvisorie. I vicini non visitati di C sono B ed E con lunghezze infinite provvisorie. Un vicino ha un vantaggio diretto dal vertice in questione.
La lunghezza del percorso calcolata da a a d, attraverso b è:
A-B-D = 4 + 9 = 13La lunghezza del percorso calcolata da A a E, attraverso B è:
A-b-e = 4 + 7 = 11La lunghezza del percorso calcolata da A a C, attraverso B è:
A-B-C = 4 + 11 = 15Quelle sono le lunghezze del percorso attraverso i vicini di B ai vicini B, dal vertice visitato, "A". Dovrebbero essere determinate anche le lunghezze del percorso provvisorio attraverso C.
La lunghezza del percorso calcolata da A a B, attraverso C è:
A-c-b = 5 + 11 = 16La lunghezza del percorso calcolata da A a E a C è:
A-c-e = 5 + 3 = 8Quelle sono le lunghezze del percorso attraverso i vicini di C ai vicini di C, dal vertice visitato, "a".
Finora tutte le lunghezze del percorso parziale calcolate provvisorie sono:
A-B-D = 4 + 9 = 13A-b-e = 4 + 7 = 11
A-B-C = 4 + 11 = 15
A-c-b = 5 + 11 = 16
A-c-e = 5 + 3 = 8
La più breve di queste lunghezze del percorso parziale è:
A-c-e = 5 + 3 = 8Quindi il vertice, C, è scelto per la via da seguire. Questo è il prossimo vertice visitato. Ogni possibile percorso attraverso B viene abbandonato. C viene quindi considerato visitato. Il vertice C viene rimosso dall'elenco non visitato. C viene inviato all'elenco visitato (per essere dopo a).
C dovrebbe avere vicini non visitati con lunghezze di percorso provvisorio. In questo caso, è B ed E. B ha vicini con lunghezze di percorso infinito, che sono d ed e. E ha vicini con lunghezze di percorso infinito, che sono d e f. Per scegliere il nodo visitato successivo, le lunghezze provvisorie per il percorso parziale da C a B ed E devono essere calcolate. I calcoli sono:
A-C-B-D = 5 + 11 + 9= 16 + 9 = 25
A-C-B-E = 5 + 11 + 7
= 16 + 7 = 23
A-C-E-D = 5 + 3 + 13
= 8 + 13 = 21
A-C-E-F = 5 + 3 + 6
= 8 + 6 = 14
Il più breve per questi percorsi in parte è:
A-C-E-F = 8 + 6 = 14A questo punto, E è la strada da percorrere. Questo è il prossimo vertice visitato. Ogni possibile percorso attraverso D viene abbandonato. E viene rimosso dall'elenco non visitato e aggiunto all'elenco visitato (per essere dopo c).
E ha vicini non visitati con lunghezze di percorso provvisorio. In questo caso, sono d e f. Se F avesse vicini non visitati, la loro provvisoria percorso di "A", la fonte, avrebbe dovuto essere infinito. Ora, la lunghezza da F a nulla è 0. Per scegliere il prossimo nodo visitato (Vertex), devono essere calcolate le lunghezze provvisorie per il percorso parziale da E a D ed E a F. I calcoli sono:
A-C-E-D-F = 5 + 3 + 13 + 2= 8 + 15 = 23
A-C-E-F- = 5 + 3 + 6 + 0
= 14 + 0 = 14
La più breve di queste lunghezze del percorso parziale è:
A-C-E-F- = 14A questo punto, F è la strada da percorrere. È considerato visitato. F viene rimosso dall'elenco non visitato e aggiunto all'elenco visitato (da essere dopo e).
F è la destinazione. E così, la lunghezza del percorso più breve dalla sorgente, a, a destinazione, f, è 14. I vertici e il loro ordine nell'elenco visitato dovrebbero essere A-C-E-F. Questo è il percorso più breve in avanti dai vertici. Per ottenere il percorso più breve inverso per i vertici, leggi l'elenco all'indietro.
Coding C ++
Il grafo
Il grafico per la rete è un array bidimensionale. È:
int g [v] [v] = 0,4,5,0,0,0,4,0,11,9,7,0,
5,11,0,0,3,0,
0,9,0,0,13,2,
0,7,3,13,0,6,
0,0,0,2,6,0;
Dovrebbe essere codificato nella funzione principale C ++. Ogni voce è la lunghezza del bordo da un vertice, lettura per riga, al vertice successivo, lettura per colonne. Un tale valore non è per più di una coppia di vertice.
Vertici come numeri
Per comodità, i vertici saranno identificati per numeri, usando la codifica ASCII, come segue:
A è 65B è 66
C è 67
D è 68
E è 69
F è 70
A è 0 + 65 = 65
B è 1 + 65 = 65
C è 2 + 65 = 65
D è 3 + 65 = 65
E è 4 + 65 = 65
F è 5 + 65 = 65
I valori di codifica per A, B, C, D, E e F sono i seguenti:
A = 0B = 1
C = 2
D = 3
E = 4
F = 5
65 verrà aggiunto a ciascuno di questi numeri per ottenere il numero ASCII corrispondente, da cui verrà ottenuta la lettera corrispondente.
Inizio del programma
L'inizio del programma è:
#includere#includere
Utilizzo dello spazio dei nomi std;
int int_max = +2'147'483'647; //infinito
#define v 6 // numero vertice in g
int shortLength = int_max;
vector non visitato = 0, 1, 2, 3, 4, 5;
vectorvisited;
Il valore per l'infinito scelto dal programmatore è 2147483647. Il numero di vertici, V (in maiuscolo), è definito (assegnato) come 6. Gli elementi del vettore non visitato (array) sono A, B, C, D, E e F, come 0, 1, 2, 3, 4, 5, corrispondenti ai numeri del codice ASCII 65, 66, 67, 68, 69, 70. Questo ordine, in questo caso, non è necessariamente un ordine predeterminato e ordinato. I vertici visitati verranno spinti nel vettore visitato nell'ordine scoperto dall'algoritmo, a cominciare dal vertice di origine.
La funzione getNeighbors ()
Questa funzione ottiene tutti i vicini prima di un vertice, a partire da subito dopo il vertice correlato precedentemente visitato. Il codice funzione è:
vectorgetNeighBors (int grafico [v] [v], int vindx, int prevVisitedX)vecTorneighbors;
per (int j = prevVisitedIndx+1; j
vicinato.push_back (j);
restituire i vicini;
La funzione Dijkstra ()
Dopo che l'indice di origine (Vertex) è stato preso in considerazione dal programma, la funzione Dijkstra () procede in modo ricorsivo fino a quando non viene considerato l'indice di destinazione (Vertex). Il codice funzione è:
void dijkstra (int grafico [v] [v], int visitedx, int visitLength)int visitedIndx = visitedIdx;
int newVisitedIndx = V;
int minLength = int_max;
int visitedLength;
int TentLength1 = 0;
vectorVisitedNbs = getNeighBors (grafico, VisitedIndx, visitedIdx);
per (int i = 0; i
vectorCurrentNbs = getNeighBors (grafico, visitato [i], visitedidx);
if (currentnbs.misurare() != 0)
per (int j = 0; j
if (TentLength2
newVisitedIndx = visitedNbs [i];
altro
VisitedLength = TentLength1; //confermato
newVisitedIndx = visitedNbs [i];
VisitedIndx = newVisitedIndx;
non visitato [visitedindx] = -1;
visitato.push_back (visitedIndx);
ShortLength = visitedLength;
if (visitedindx< V -1)
Dijkstra (grafico, visitedIndx, visitedLength);
La funzione startdijkstra ()
L'algoritmo di Dijkstra inizia con questa funzione per gestire la situazione del codice sorgente. Il codice funzione è:
void startdijkstra (int grafico [v] [v], int srcvidx)int visitedIndx = srcvidx;
non visitato [visitedindx] = -1;
visitato.push_back (visitedIndx);
int visitedLength = 0;
Dijkstra (grafico, visitedIndx, visitedLength);
I segmenti di codice di cui sopra possono essere assemblati nell'ordine dato per formare il programma.
La funzione principale C ++
Una funzione principale C ++ adatta è:
int main (int argc, char ** argv)int g [v] [v] = 0,4,5,0,0,0,
4,0,11,9,7,0,
5,11,0,0,3,0,
0,9,0,0,13,2,
0,7,3,13,0,6,
0,0,0,2,6,0;
int SourceverTex = 0;
startdijkstra (g, sourcevertex);
cout<
cout<
Conclusione
La complessità del tempo è il tempo di esecuzione relativo. Supponendo che l'ordinamento dei vertici (vicini) sia buono, si dice che il programma di cui sopra abbia la seguente complessità del tempo:
O ((| e | + | v |) log | v |)dove | E | è il numero di bordi, | v | è il numero di vertici e un registro è log2. Il big-o con le sue parentesi, () è un modo per indicare che l'espressione nella parentesi è la complessità del tempo (tempo di esecuzione relativo).
La complessità del tempo peggiore per l'algoritmo di Dijkstra è: O (| V |2)
[/cc]