Dijkstras algoritmetidskompleksitet
Tenk på følgende byer: A, B, C, D, E og F forbundet med veier:
Disse byene er forbundet med veier (som kan antas å være rett). Veilengden fra byen A til by B er 4 enheter; det er ikke trukket til skala. Veilengden fra byen A til Town C er 5 enheter; det er ikke trukket til skala. Lengden fra by B til by E er 11 enheter, ikke trukket til skala. Veiene mellom andre byer er på samme måte indikert.
Byene: A, B, C, D, E og F er toppunktene til en graf. Veiene er kantene på grafen. Imidlertid vil denne grafen være representert i en matematisk datastruktur, annerledes enn dens geografiske utforming.
Dijkstras algoritme kan brukes til å finne den korteste banen mellom et kildehode (si A) og alle andre toppunkt. For ytterligere enkelhet vil denne artikkelen ta sikte på å se etter den korteste veien fra A til E.
Det er forskjellige veier fra A til E, med forskjellige lengder, som følger:
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
Fra denne oppføringen er den korteste banen A-C-E-F, med en total lengde på 14 enheter.
Hovedmålet med denne artikkelen er å finne kjøretid. Tiden vil ikke bli gitt på sekunder eller minutter. Det er den relative totale utførelsestiden, kalt tidskompleksitet, som vil bli gitt. C ++ koding leveres også.
Graf å bruke
Tidskompleksiteten (relativ kjøretid) avhenger hovedsakelig av typen matematisk graf som brukes til å representere den geografiske utformingen. Det avhenger også av algoritmen (en annen type algoritme) som brukes til å sortere de nærliggende toppunktene til hvert toppunkt i den totale algoritmen (Dijkstras algoritme). Sortering av nabovannene blir ikke adressert i denne artikkelen.
Den matematiske grafen som er valgt for denne artikkelen, kalles adjacency matrix. Det er:
Radoverskriftene er bymennene fra A til F. Kolonneoverskriftene er de samme bymennene fra A til F. Hver oppføring er lengden på en vei fra en by til den neste. Lengden på en vei fra en by til seg selv er null. Lengden på en vei fra en by til en annen, etter å ha hoppet over en eller flere byer, er også null. Bare direkte veier blir vurdert. Hver oppføring er lokalisert, først etter rad og deretter etter kolonne. Igjen er hver oppføring lengden på en vei, uten å hoppe over en by, og ikke til byen selv. Denne matrisen er en matematisk representasjon av det geografiske nettverket gitt ovenfor.
Så matrisen består av kanter, med rad- og kolonneoverskriftene til de samme toppunktene. Matrisen er hovedstrukturen som trengs i programmet. To andre vektorer (matriser) brukes i dette grunnleggende programmet.
Dijkstras algoritme
Dijkstras algoritme ser etter den korteste banen mellom to hjørner i en graf (nettverk). Ovennevnte matrise er grafen, som tilsvarer ovennevnte geografiske nettverk. For enkelhets skyld vil programmet i denne artikkelen se etter den korteste banen mellom et kildeutvikling og en destinasjons toppunkt. Nettopp, programmet vil se etter den korteste veien fra kildehåren, A, til destinasjonsutstyret, f.
Algoritmen, som relevant for denne oppgaven, er som følger:
- Alle toppunktene er merket som uovertruffen. På dette tidspunktet opprettes det et sett med alle uovertruffelige toppunkter.
- Tilordne en tentativ banelengdeverdi til alle toppunktene: banelengden fra kilde til kilden tildeles en verdi på null; banelengden fra kilde til alle andre toppunkt tildeles den ene verdien av uendelig, i.e., en verdi som er høyere enn den høyeste veien som er mulig, i grafen. Verdien av hvert toppunkt vil bli endret minst en gang, fra en høy verdi til en lavere verdi, ettersom algoritmen fortsetter. Mulige toppunkter for den komplette korteste banen vil være fokusert på, fra og med kilden Vertex (A). Toppunktet med fokus kalles dagens toppunkt. Det nåværende toppunktet har naboer, bedre visualisert fra selve nettverket (geografisk utforming) ovenfor.
- Det er det nåværende toppunktet, og det er det besøkte toppunktet. Det ville faktisk være mer enn en besøkte toppunkt i en kjede når algoritmen fortsetter. Alle tidligere hjørner som ble vurdert som besøkes er i den korteste komplette banen som utvikles, fra og med kilden fra kilden. Banelengden på den siste besøkte toppunktet er kjent (bør være kjent). Et toppunkt blir erklært besøkt når banelengden er bekreftet. Det besøkte Vertex gir minst mulig banelengde fra kilden så langt, ettersom algoritmen pågår. De uvisede naboene i det nåværende toppunktet, bortsett fra dens umiddelbare tidligere besøkte nabo, har tentative verdier (banelengder fra kilden), hvorav noen fremdeles kan være uendelig (veldig høy verdi). For hver uovertruffen nabo og det nåværende toppunktet beregnes en ny tentativ banelengde som følger: banens lengde på den tidligere besøkte toppunkt uvisnet nabo. Hvis dette resultatet er mindre enn det som var der, ettersom den tentative banelengden fra kilden til den uvisede naboen til det nåværende toppunktet, blir denne beregnede verdien den nye tentative verdien for naboen til det nåværende toppunktet. Det vil si at den nye tentative baneverdien for en uovertruffen toppunkt beregnes gjennom det nåværende toppunktet fra det tidligere besøkte toppunktet.
- Det kan være mer enn en strømlansjer. Når alle naboene i hvert nåværende toppunkt har fått tilgang til og gitt nye passende tentative banelengder, anses det gjeldende toppunktet med minst banelengde fra kilden (minst verdi) som besøkes. Siden den hadde minst mulig verdi, bekreftes minst mulig verdi som den korteste delbanelengden så langt. Det tidligere besøkte Vertex fjernes fra det uunngåelige toppunktsettet. Et besøkt Vertex vil aldri bli sjekket igjen. Eventuelle besøk etter ville ha en større banelengde.
- De to foregående trinnene gjentas, i orden, for enhver neste nåværende toppunkt som blir et besøkt toppunkt. Denne repetisjonen fortsetter til destinasjonsutstyret er nådd. Destinasjonsutstyret kan være et hvilket som helst toppunkt etter kilden. For enkelhets skyld er imidlertid den siste toppunktet, f i ovennevnte nettverk, blitt valgt som destinasjonsutstyr for denne artikkelen.
- Når algoritmen skrider frem, skal hver foreldre (tidligere besøkt) toppunkt, og hvert barn (neste besøkt) toppunkt, av den korteste banen, registreres i tilfelle den korteste banen, av toppunktene, så vel som den korteste banen etter lengde, er nødvendig (( spurte om). Når målet. Når det gjelder banelengden, ble den beregnet etter hvert som algoritmen gikk videre.
Illustrasjon Dijkstras algoritme
Ovennevnte vei
Nettverket brukes til å illustrere Dijkstras algoritme. Det er avkortet nedenfor for enkel referanse.
Det begynner ved kilden, "a" med en banelengde på null. “A” blir betraktet som besøkt og fjernet fra den uvisede listen (sett). “A” blir sendt til en besøkt liste i tilfelle stien med toppunkt vil være påkrevd.
Banelengdene fra A til B er:
A-B = 4A-C-B = 5 + 11 = 16
Mellom 4, 16 og uendelig (det var der), er 4 minst. Så B får den tentative verdien på 4 som banelengde.
Banelengdene fra A til C er:
A-C = 5A-B-C = 4 + 11 = 15
Mellom 5, 15 og uendelig (det var der), er 5 minst. Så C får den tentative verdien på 5 som banelengde.
B og C var de uvisede naboene til en. For øyeblikket har hver en tentativ banelengde. Mellom B og C må et toppunkt velges bidra til den endelige totale banen. B og C har også naboer.
De uvisede naboene til B er d, e og c, med tentative uendelige lengder. De uvisede naboene til C er B og E med tentative uendelige lengder. En nabo har en direkte kant fra det aktuelle toppunktet.
Banelengden beregnet fra A til D, gjennom B er:
A-B-D = 4 + 9 = 13Banelengden beregnet fra A til E, gjennom B er:
A-B-E = 4 + 7 = 11Banelengden beregnet fra A til C, gjennom B er:
A-B-C = 4 + 11 = 15Dette er banelengder gjennom B til Bs naboer, fra det besøkte Vertex, “A”. Den tentative banelengdene gjennom C bør også bestemmes.
Banelengden beregnet fra A til B, gjennom C er:
A-C-B = 5 + 11 = 16Banelengden beregnet fra A til E til C er:
A-C-E = 5 + 3 = 8Dette er banelengder gjennom C til Cs naboer, fra det besøkte Vertex, “A”.
Alle de tentative beregnede delvestielengdene så langt er:
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
Den korteste av disse delvislengdene er:
A-C-E = 5 + 3 = 8Så toppunktet, C, er valgt for veien videre. Dette er neste besøkte Vertex. Enhver mulig vei gjennom B blir forlatt. C blir deretter ansett som besøkt. Vertex C fjernes fra den uovertrufne listen. C sendes til den besøkte listen (for å være etter en).
C skal ha uovertede naboer med tentative banelengder. I dette tilfellet er det B og E. B har naboer med uendelige banelengder, som er d og e. E har naboer med uendelige banelengder, som er d og f. For å velge den neste besøkte noden, må de tentative del-bane lengder fra C til B og E beregnes. Beregningene er:
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
Den korteste for disse delstiene er:
A-C-E-F = 8 + 6 = 14På dette tidspunktet er E veien videre. Dette er neste besøkte Vertex. Enhver mulig vei gjennom D blir forlatt. E fjernes fra den uovertrufne listen og legges til den besøkte listen (for å være etter C).
E har uovertede naboer med tentative banelengder. I dette tilfellet er det D og F. Hvis F hadde uovertede naboer, burde deres tentative banelengder fra “A”, kilden, ha vært uendelig. Nå er lengden fra f til ingenting 0. For å velge den neste besøkte noden (Vertex), må den tentative del-bane lengder fra E til D og E til F beregnes. Beregningene er:
A-C-E-D-F = 5 + 3 + 13 + 2= 8 + 15 = 23
A-C-E-F- = 5 + 3 + 6 + 0
= 14 + 0 = 14
Den korteste av disse delvislengdene er:
A-C-E-F- = 14På dette tidspunktet er F veien videre. Det anses som besøkt. F fjernes fra den uovertrufne listen og legges til den besøkte listen (for å være etter E).
F er destinasjonen. Og så, den korteste banelengden fra kilde, a, til destinasjon, f, er 14. Vertiver og deres bestilling i den besøkte listen skal være A-C-E-F. Dette er den korteste banen med toppunktene. For å oppnå den omvendte korteste banen med toppunktene, les listen bakover.
C ++ koding
Grafen
Grafen for nettverket er en todimensjonal matrise. Det er:
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;
Den skal kodes i C ++ hovedfunksjonen. Hver oppføring er lengden på kanten fra en toppunkt, lesing-for-rader, til neste toppunkt, lese-for-kolonner. En slik verdi er ikke for mer enn ett toppunktpar.
Hjørner som tall
For enkelhets skyld vil toppunktene bli identifisert med tall ved å bruke ASCII -koding, som følger:
A er 65B er 66
C er 67
D er 68
E er 69
F er 70
A er 0 + 65 = 65
B er 1 + 65 = 65
C er 2 + 65 = 65
D er 3 + 65 = 65
E er 4 + 65 = 65
F er 5 + 65 = 65
Kodingsverdiene for A, B, C, D, E og F er som følger:
A = 0B = 1
C = 2
D = 3
E = 4
F = 5
65 vil bli lagt til hvert av disse tallene for å få det tilsvarende ASCII -nummeret, hvorfra det tilsvarende bokstavet vil oppnås.
Begynnelsen av programmet
Begynnelsen på programmet er:
#inkludere#inkludere
ved hjelp av navneområdet STD;
int int_max = +2'147'483'647; //evighet
#Define V 6 // toppunktnummer i G
int kortestlengde = int_max;
vektor unvisited = 0, 1, 2, 3, 4, 5;
Vectorvisited;
Verdien for uendelig valgt av programmereren er 2147483647. Antall hjørner, V (i store bokstaver), er definert (tildelt) som 6. Elementene i den uvisede vektoren (array) er A, B, C, D, E og F, som 0, 1, 2, 3, 4, 5, tilsvarende ASCII -kodetallene 65, 66, 67, 68, 69, 70. Denne ordren er i dette tilfellet ikke nødvendigvis en forhåndsbestemt, sortert ordre. Besøkte toppunkter vil bli dyttet inn i den besøkte vektoren i den rekkefølgen som ble oppdaget av algoritmen, som begynner med kilden Vertex.
Getneighbors () -funksjonen
Denne funksjonen oppnår alle naboene foran et toppunkt, fra like etter den tidligere besøkte relaterte toppunktet. Funksjonskoden er:
VectorGetNeighbors (int Graph [V] [V], int Vindx, Int PrevvisitedIndx)Vectorneighbors;
for (int j = previsitedIndx+1; j
naboer.push_back (j);
returner naboer;
Dijkstra () -funksjonen
Etter at kildeindeksen (Vertex) har blitt vurdert av programmet, går Dijkstra () -funksjonen i handling rekursivt til destinasjonsindeksen (Vertex) blir vurdert. Funksjonskoden er:
void dijkstra (int graf [v] [v], int visitedIdx, int VisitLength)int VisitedIndx = VisitedIdx;
int newvisitedindx = v;
int minlength = int_max;
int VisitedLength;
int tentlength1 = 0;
VectorVisitedNBS = GetNeighbors (Graph, VisitedIndx, VisitedIdx);
for (int i = 0; i
VectorCurrentNBS = getNeighbors (graf, VisitedNBS [i], VisitedIdx);
if (currentNBs.størrelse() != 0)
for (int j = 0; j
if (tentlength2
newVisitedIndx = VisitedNBS [i];
annet
VisitedLength = Tentlength1; // bekreftet
newVisitedIndx = VisitedNBS [i];
BesøktindX = newvisitedIndx;
uvisnet [VisitedIndx] = -1;
besøkte.Push_back (VisitedIndx);
kortestlengde = VisitedLength;
if (besøkteindx< V -1)
Dijkstra (graf, VisitedIndx, VisitedLength);
Startdijkstra () -funksjonen
Dijkstras algoritme starter med denne funksjonen for å håndtere kildekodesituasjonen. Funksjonskoden er:
void startdijkstra (int graf [v] [v], int srcvidx)int VisitedIndx = SRCVIDX;
uvisnet [VisitedIndx] = -1;
besøkte.Push_back (VisitedIndx);
int VisitedLength = 0;
Dijkstra (graf, VisitedIndx, VisitedLength);
Ovennevnte kodesegmenter kan settes sammen i den rekkefølgen som er gitt for å danne programmet.
C ++ hovedfunksjonen
En passende C ++ hovedfunksjon er:
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<
Konklusjon
Tidskompleksitet er den relative kjøretiden. Forutsatt at sortering av toppunktene (naboer) er bra, sies det ovennevnte programmet å ha følgende tidskompleksitet:
O ((| e | + | v |) log | v |)hvor | e | er antall kanter, | V | er antall hjørner, og en logg er logg2. Big-O med parentesene, () er en måte å indikere at uttrykket i parentesen er tidskompleksitet (relativ kjøretid).
Den verste tidskompleksiteten for Dijkstras algoritme er: O (| V |2)
[/cc]