L'algoritmo di Dijkstra C ++

L'algoritmo di Dijkstra è anche noto come l'algoritmo del percorso più breve possibile. È la procedura per trovare il percorso più breve tra i nodi/ bordi del grafico. Il grafico più corto di un albero viene creato a partire dal vertice di origine a tutti gli altri punti del grafico.

Algoritmo

• Prima dell'implementazione diretta del grafico Dijkstra nel linguaggio di programmazione C ++, dobbiamo comprendere il funzionamento di questo algoritmo grafico.
• Il primo passo è la creazione di "SPTSET", che è abbreviato come set di alberi più corti; Memorizza il record di quei vertici che sono inclusi nel percorso più breve. Nella fase iniziale, questo set è dichiarato null.
• Nel passaggio successivo, in primo luogo, tutti questi valori ai nodi sono dichiarati infiniti, poiché fino ad ora non conosciamo il peso dei percorsi.
• Scegli un vertice "u" che non è già presente in spset ed è di valore minimo. Quindi includerlo su SPTSET. Successivamente, aggiorna i valori di distanza di tutti quei nodi che sono vertici adiacenti di "U."Questo è fatto sotto il ciclo fino a quando SPTSET non può contenere tutti i vertici.

Implementazione dell'algoritmo grafico di Dijkstra

Ecco l'implementazione del grafico Dijkstra, in cui un programma è scritto per la rappresentazione della matrice di adiacenza di quel grafico. Avvia il programma aggiungendo due librerie molto essenziali per la realizzazione del programma in linguaggio di programmazione C ++ che ci rende in grado di utilizzare le funzionalità CIN e COUT.

#includere
#includere

Dopo aver descritto le librerie, ora forniremo le dimensioni o i vertici del grafico in cui abbiamo bisogno del percorso più breve. Abbiamo dato 9 vertici, il che significa che la matrice è un quadrato di [9] [9].

#define v 9

"V" è per i vertici. Poiché l'algoritmo richiede molti passaggi per eseguire l'attività fornita, ogni passaggio o processo è diviso in funzioni separate per eseguirle in modo che il codice sia chiaro e non vi è alcuna ambiguità per quanto riguarda la logica. Inoltre, la complessità viene anche rimossa.

La funzione viene creata qui per cercare il vertice che ha un valore di distanza minimo; contiene l'insieme di vertici che non sono inclusi nell'albero con il percorso più corto. La funzione conterrà l'array di distanza e uno spset di tipo bool, il set di alberi percorso più corto e l'array come parametro della funzione. All'interno della funzione, il valore minimo viene inizializzato dichiarando una variabile di tipo intero che memorizzerà il valore restituito. Vengono introdotti due variabili, max e il min_index.

Int min = int_max, min_index;

A per loop è usato qui; in cui viene preso un vertice iniziale in tutti i vertici, il ciclo continuerà fino a quando tutti i vertici non saranno attraversati. Una condizione viene applicata qui utilizzando un'istruzione if che verifica se il set di percorso più breve è falso mezzi, è vuoto in questo momento e la distanza del vertice è inferiore a quella del valore minimo del vertice, che viene dichiarato in precedenza, quindi assegnare il valore corrente del vertice come min e il min_index conterrà anche lo stesso valore del vertice.

Min = dist [v], min_index = v;

Dopo aver calcolato il valore minimo del vertice, successivo è il processo di creazione di una funzione che visualizzerà l'array di distanza che è stato costruito in precedenza. Un ciclo itederà ogni indice a cui verrà accessibile e visualizzato. Innanzitutto, il numero di vertice viene visualizzato a partire dal valore zero e la distanza del vertice dalla sorgente viene menzionata anche qui con una sequenza. Questa funzione è dichiarata qui, ma verrà chiamata più avanti nel programma quando l'intero percorso viene calcolato come la distanza più breve.

La parte principale dell'intero codice sorgente è ora dichiarata, in cui viene calcolata l'implementazione del percorso più breve della source. Un grafico sarà rappresentato dalla rappresentazione della matrice di adiacenza. Questa funzione prenderà una matrice del grafico e la sorgente come valori dei parametri che fungeranno da input per il calcolo della distanza. Innanzitutto, all'interno della funzione, dichiareremo l'array di output che conterrà il percorso più breve dalla sorgente a un punto specifico. In secondo luogo, viene dichiarato un array variabile booleano, che restituirà vero se il vertice è incluso nel determinare il percorso più breve all'inizio.

Int dist [v]; bool sptset [v];

Tutte le distanze saranno impostate come infinite e l'array di percorso dell'albero più corto è falso. Con l'aiuto di un ciclo, tutto questo processo avrà luogo.

All'interno del ciclo, il vertice a distanza minimo viene raccolto dal set di vertici che non vengono ancora elaborati. Nella prima iterazione, 'u' è sempre uguale al vertice di origine.

Int u = Mindistance (dist, SptSet);

Quei vertici che vengono scelti e attraversati sono raccolti e contrassegnati come elaborati impostando la variabile booleana è vero.

sptset [u] = true;

Quando viene aggiunto un vertice, vengono anche controllati tutti i vertici adiacenti a quel particolare vertice; Questo richiede un aggiornamento. Quindi aggiorneremo il valore di "dist" dei vertici adiacenti di quei vertici che sono stati picchetti fino ad ora.

All'interno di questo per loop, aggiorneremo dist [v] se e solo se non si trova nello SPTSET, c'è una linea chiamata bordo dal vertice U a V e il peso totale del percorso che inizia da "SRC" a "v" passando attraverso "u" è più piccolo del valore corrente presente nella dist [v].

Dist [v] = dist [u] + grafico [u] [v];

Successivamente, la funzione di stampa che abbiamo dichiarato sopra viene chiamata passando l'array dist [] come parametro.

printsolution (dist);

Nel programma principale, creiamo un grafico a matrice 9*9. E poi, la funzione richiede la funzione Dijkstra, attraverso la quale viene passato il grafico.

Salva l'intero codice. Compilare il codice utilizzando un compilatore G ++ nel terminale Ubuntu. '-o' è un simbolo che salva l'output del file.

$ g ++ -o dij dij.C
$ ./DIJ

Puoi vedere che tutti i vertici in ciascuna linea separata vengono visualizzati insieme alla distanza di ogni vertice dalla sorgente.

Questo codice aiuta a calcolare la distanza più breve, ma non supporta il calcolo delle informazioni sul percorso. Questo codice sorgente è buono per i grafici non diretti ma può essere possibile utilizzare anche per i grafici diretti. Usando questo codice, possiamo trovare la distanza più breve dal punto di origine a tutti gli altri vertici nel grafico.

La complessità temporale del grafico Dijkstra

Parleremo della complessità temporale dell'implementazione. È:

0 (V^2).

Questo può essere ridotto a 0 (log v) utilizzando il processo del mucchio binario. Il grafico Dijkstra non è per i grafici che hanno pesi negativi.

Conclusione

Questo articolo contiene il processo di ricerca della distanza più breve tra il nodo di origine al resto dei nodi. Ci possono essere molti approcci a questo. Ma il grafico Dijkstra è uno dei migliori meccanismi a questo scopo. È progettato per grafici non diretti. Abbiamo spiegato il processo passo dopo passo con il codice sorgente per renderlo vivido per i nuovi utenti. Speriamo che questo sforzo sarà all'altezza dei lettori.