Dijkstras algoritme C ++

Dijkstras algoritme er også kjent som den kortest mulige banalgoritmen. Det er prosedyren å finne den korteste banen mellom nodene/ kantene på grafen. Den korteste grafen til et tre opprettes ved å starte fra kilden til alle de andre punktene i grafen.

Algoritme

• Før direkte implementering av Dijkstra -grafen på programmeringsspråket C ++, må vi forstå arbeidet med denne grafalgoritmen.
• Det første trinnet er etableringen av "SPTSET", som er forkortet som det korteste bane -settet; Den lagrer posten til de toppunktene som er inkludert i den korteste banen. I det første stadiet er dette settet erklært som null.
• I neste trinn blir først alle disse verdiene ved nodene erklært som uendelige, da vi ikke vet vekten av stiene før nå.
• Velg et toppunkt “U” som ikke er til stede allerede i SPTSET og er av minimumsverdi. Inkluder det deretter til SPTSET. Etter det, oppdater avstandsverdiene til alle nodene som er tilstøtende hjørner til “u.”Alt dette gjøres under løkken til SPTSET kan inneholde alle toppunktene.

Implementering av Dijkstras grafalgoritme

Her er implementeringen av Dijkstra -grafen, der et program er skrevet for adjacency Matrix -representasjonen av den grafen. Start programmet ved å legge til to biblioteker veldig viktige for gjennomføringen av programmet i C ++ programmeringsspråk som gjør at vi er i stand til å bruke CIN- og COUT -funksjoner.

#inkludere
#inkludere

Etter å ha beskrevet bibliotekene, vil vi nå gi størrelsen eller toppunktene på grafen vi trenger den korteste banen. Vi har gitt 9 hjørner som betyr at matrisen er en kvadrat på [9] [9].

#Define V 9

“V” er for toppunktene. Siden algoritmen krever mange trinn for å utføre den oppgitte oppgaven, er hvert trinn eller prosess delt inn i separate funksjoner for å utføre dem slik at koden er klar og det ikke er noen tvetydighet angående logikken. Dessuten fjernes kompleksiteten også.

Funksjonen opprettes her for å søke i toppunktet som har en minimum avstandsverdi; Den inneholder settet med hjørner som ikke er inkludert i treet som har den korteste banen. Funksjonen vil inneholde avstandsarrayen og en BOOL -type SPTSET, det korteste banet -tresettet og matrisen som en parameter for funksjonen. Inne i funksjonen initialiseres minimumsverdien ved å erklære en variabel av heltallstype som vil lagre den returnerte verdien. To variabler, maks og min_index blir introdusert.

Int min = int_max, min_index;

A for sløyfe brukes her; Der det er tatt et startutstyr i alle hjørner, vil sløyfen fortsette til alle toppunktene er krysset. En tilstand brukes her ved å bruke en IF -uttalelse som sjekker om det korteste banesettet er falske midler, den er tom akkurat nå, og avstanden til toppunktet er mindre enn den for minimumsverdien til toppunktet, som er erklært tidligere, tildel deretter den nåværende verdien av toppunktet som Min, og min_index vil også inneholde samme verdi av toppunktet.

Min = dist [v], min_index = v;

Etter at minimumsverdien til toppunktet er beregnet, er den neste prosessen med å lage en funksjon som vil vise avstandsarrayen som ble konstruert tidligere. En sløyfe vil iterere hver indeks som vil få tilgang til og vises. Først vises toppunktnummeret fra nullverdien, og avstanden til toppunktet fra kilden er også nevnt her med en sekvens. Denne funksjonen er erklært her, men den vil bli ringt senere i programmet når hele banen beregnes som den korteste avstanden.

Hoveddelen av hele kildekoden er deklarert nå, der implementeringen av den korteste banen for en kilde er beregnet. En graf vil bli representert av adjacency matrix -representasjonen. Denne funksjonen vil ta en grafmatrise og kilden som parameterverdier som vil fungere som input for avstandsberegning. For det første, inne i funksjonen, vil vi erklære utgangsarrayen som vil inneholde den korteste banen fra kilden til et bestemt punkt. For det andre er en boolsk variabel matrise erklært, noe som vil komme tilbake hvis toppunktet er inkludert i å bestemme den korteste banen ved starten av.

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

Alle avstandene vil bli satt som uendelige, og den korteste tresti -arrayen er falsk. Ved hjelp av en sløyfe vil all denne prosessen finne sted.

Inne. I den første iterasjonen er 'U' alltid lik kildens toppunkt.

Int u = Mindistance (dist, sptset);

De toppunktene som er valgt og krysset er valgt og merket som behandlet ved å stille den boolske variabelen er sant.

sptset [u] = true;

Når en toppunkt legges til, blir også alle toppunktene ved siden av det aktuelle toppunktet sjekket; Dette trenger en oppdatering. Så vi vil oppdatere verdien av "DIST" for de tilstøtende toppunktene til de toppunktene som har vært stakitt til nå.

Inne i dette for Loop vil vi oppdatere DIST [V] Hvis og bare hvis det ikke er i SPTSET, er det en linje som kalles en kant fra toppunktet U til V, og den totale vekten på banen som starter fra “SRC” til “V” ved å passere gjennom “U” er mindre enn den nåværende verdien som er til stede i Dist [V].

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

Etter det kalles utskriftsfunksjonen som vi har erklært ovenfor ved å passere DIST [] -arrayen som en parameter.

PrintSolution (DIST);

I hovedprogrammet lager vi en 9*9 Matrix -graf. Og så blir funksjonskallet for Dijkstra -funksjonen laget, som grafen sendes.

Lagre hele koden. Sett sammen koden ved å bruke en G ++ kompilator i Ubuntu -terminalen. '-o' er et symbol som lagrer utdataene fra filen.

$ g ++ -o dij dij.c
$ ./dij

Du kan se at alle toppunktene i hver separate linje vises sammen med avstanden til hvert toppunkt fra kilden.

Denne koden er med på å beregne den korteste avstanden, men den støtter ikke beregning av informasjonen om banen. Denne kildekoden er bra for de rettede grafene, men kan være mulig å bruke for de rettede grafene også. Ved å bruke denne koden, kan vi finne den korteste avstanden fra kildepunktet til alle andre hjørner i grafen.

Tidskompleksiteten til Dijkstra -grafen

Vi vil snakke om tidskompleksiteten i implementeringen. Det er:

0 (V^2).

Dette kan reduseres til 0 (e log V) ved å bruke prosessen med den binære haugen. Dijkstra -grafen er ikke for grafene som har negative vekter.

Konklusjon

Denne artikkelen inneholder prosessen med å finne den korteste avstanden mellom kildeknuten til resten av nodene. Det kan være mange tilnærminger til dette. Men Dijkstra -grafen er en av de beste mekanismene for dette formålet. Den er designet for rettede grafer. Vi har forklart prosessen trinn for trinn med kildekoden for å gjøre den levende for de nye brukerne. Vi håper at denne innsatsen vil være opp til merket for leserne.