Algoritmul de arțar al lui Dijkstra. Un exemplu de rezolvare a problemei de a găsi calea cea mai scurtă folosind algoritmul lui Dijkstra

05.03.2020 Photoshop 3D

Dintre mulți algoritmi pentru găsirea celor mai scurte rute pe un grafic, pe Habré am găsit doar o descriere a algoritmului Floyd-Warshall. Acest algoritm găsește cele mai scurte căi între toate vârfurile graficului și lungimea lor. În acest articol, voi descrie principiul de funcționare al algoritmului lui Dijkstra, care găsește rutele optime și lungimile acestora între un anumit vârf (sursă) și toate celelalte vârfuri ale graficului. Dezavantajul acestui algoritm este că nu va funcționa corect dacă graficul are arce de greutate negativă.

De exemplu, luați următorul grafic direcționat G:

Putem reprezenta acest grafic ca o matrice C:

Să luăm vârful 1 ca sursă. Aceasta înseamnă că vom căuta cele mai scurte rute de la vârful 1 la vârfurile 2, 3, 4 și 5.
Acest algoritm parcurge toate vârfurile graficului și le atribuie etichete, care reprezintă distanța minimă cunoscută de la vârful sursă la un anumit vârf. Să ne uităm la acest algoritm folosind un exemplu.

Să atribuim o etichetă egală cu 0 primului vârf, deoarece acest vârf este sursa. Vom atribui etichete egale cu infinit nodurilor rămase.

Apoi, selectăm un vârf W care are o etichetă minimă (în prezent este vârful 1) și luăm în considerare toate vârfurile la care există o cale de la vârful W care nu conține vârfuri intermediare. Fiecăruia dintre vârfurile considerate atribuim o etichetă egală cu suma etichetei W și lungimea drumului de la W la vârful considerat, dar numai dacă suma rezultată este mai mică decât valoarea anterioară a etichetei. Dacă suma nu este mai mică, atunci lăsăm marca anterioară neschimbată.

După ce am luat în considerare toate nodurile către care există o cale directă de la W, marchem vârful W ca fiind vizitat și îl selectăm dintre cele ne vizitate încă pe cel care are valoarea minimă a etichetei, acesta va fi următorul vârf al lui W. În în acest caz, acesta este vârful 2 sau 5. Dacă există mai multe vârfuri cu aceleași etichete, atunci nu contează pe care o alegem ca W.

Vom selecta vârful 2. Dar nu există o cale de ieșire din el, așa că marchem imediat acest vârf ca vizitat și trecem la următorul vârf cu eticheta minimă. De data aceasta, doar vârful 5 are eticheta minimă. Să luăm în considerare toate vârfurile la care există căi directe din 5, dar care nu au fost încă marcate ca vizitate. Din nou găsim suma etichetei vârfului W și greutatea muchiei de la W la vârful curent, iar dacă această sumă este mai mică decât eticheta anterioară, atunci înlocuim valoarea etichetei cu suma rezultată.

Pe baza imaginii, putem observa că etichetele vârfurilor 3 și 4 au devenit mai mici, adică s-a găsit un traseu mai scurt către aceste vârfuri de la vârful sursă. Apoi, marcați al 5-lea vârf ca vizitat și selectați următorul vârf care are eticheta minimă. Repetăm toți pașii de mai sus atâta timp cât există vârfuri nevizitate.

După parcurgerea tuturor pașilor, obținem următorul rezultat:

Există și un vector P, pe baza căruia puteți construi cele mai scurte rute. Numărul de elemente ale acestui vector este egal cu numărul de vârfuri din grafic. Fiecare element conține ultimul vârf intermediar pe calea cea mai scurtă dintre vârful sursă și vârful destinație. La începutul algoritmului, toate elementele vectorului P sunt egale cu vârful sursă (în cazul nostru, P = (1, 1, 1, 1, 1)). Apoi, în etapa de recalculare a valorii etichetei pentru vârful în cauză, dacă eticheta vârfului în cauză se schimbă într-una mai mică, scriem valoarea vârfului curent W în tabloul P. De exemplu: al 3-lea vârf avea o etichetă cu valoarea „30”, cu W = 1. Apoi, la W=5, eticheta celui de-al 3-lea vârf s-a schimbat în „20”, prin urmare vom scrie valoarea în vectorul P - P=5. De asemenea, când W=5, valoarea etichetei la al 4-lea vârf s-a schimbat (a fost „50”, a devenit „40”), ceea ce înseamnă că trebuie să atribuiți valoarea W - P=5 celui de-al 4-lea element al vectorul P. Ca rezultat, obținem vectorul P = (1, 1, 5, 5, 1).

Știind că fiecare element al vectorului P conține ultimul vârf intermediar pe calea dintre sursă și vârful final, putem obține chiar cel mai scurt traseu.

Algoritmul lui Dijkstra este un algoritm grafic inventat de omul de știință olandez Edsger Dijkstra în 1959. Găsește cele mai scurte căi de la unul dintre vârfurile graficului la toate celelalte. Algoritmul funcționează numai pentru grafice fără muchii de greutate negativă.

Să luăm în considerare execuția algoritmului folosind exemplul graficului prezentat în figură.

Să presupunem că trebuie să găsiți cele mai scurte distanțe de la primul vârf la toate celelalte.

Cercurile indică vârfurile, liniile indică căile dintre ele (marginile graficului). Numerele vârfurilor sunt indicate în cercuri, iar „prețul” lor este indicat deasupra marginilor - lungimea căii. Lângă fiecare vârf există un semn roșu - lungimea celei mai scurte căi către acest vârf de la vârful 1.

Primul pas. Să ne uităm la pasul algoritmului lui Dijkstra pentru exemplul nostru. Vârful 1 are eticheta minimă. Vecinii săi sunt vârfurile 2, 3 și 6.

Primul vecin al vârfului 1 este vârful 2, deoarece lungimea căii către acesta este minimă. Lungimea căii în el prin vârful 1 este egală cu suma valorii etichetei vârfului 1 și lungimea muchiei care merge de la 1 la 2, adică 0 + 7 = 7. Aceasta este mai mică decât eticheta curentă a vârfului 2, infinit, deci noua etichetă este al 2-lea vârf este 7.

Efectuăm o operație similară cu alți doi vecini ai primului vârf - al 3-lea și al 6-lea.

Toți vecinii vârfului 1 sunt verificați. Distanța minimă actuală până la vârful 1 este considerată finală și nu poate fi revizuită (că acesta este într-adevăr cazul a fost dovedit prima dată de E. Dijkstra). Să o tăiem din grafic pentru a marca faptul că acest vârf a fost vizitat.

Al doilea pas. Se repetă pasul algoritmului. Din nou găsim „cel mai apropiat” dintre vârfurile nevizitate. Acesta este vârful 2 cu eticheta 7.

Din nou încercăm să reducem etichetele vecinilor vârfului selectat, încercând să trecem în ele prin al 2-lea vârf. Vecinii vârfului 2 sunt vârfurile 1, 3 și 4.

Primul (în ordine) vecin al vârfului 2 este vârful 1. Dar acesta a fost deja vizitat, așa că nu facem nimic cu primul vârf.

Următorul vecin al vârfului 2 este vârful 3, deoarece are eticheta minimă a vârfurilor marcate ca nevizitate. Dacă treceți la el prin 2, atunci lungimea unei astfel de căi va fi egală cu 17 (7 + 10 = 17). Dar eticheta curentă a celui de-al treilea vârf este 9, care este mai mică de 17, deci eticheta nu se schimbă.

Un alt vecin al vârfului 2 este vârful 4. Dacă mergeți la el prin al 2-lea, atunci lungimea unei astfel de căi va fi egală cu suma celei mai scurte distanțe până la al 2-lea vârf și distanța dintre vârfurile 2 și 4, adică , 22 (7 + 15 = 22) . Din 22<, устанавливаем метку вершины 4 равной 22.

Toți vecinii vârfului 2 au fost vizualizați, înghețăm distanța până la acesta și îl marchem ca vizitat.

Al treilea pas. Repetăm pasul algoritmului, selectând vârful 3. După „procesarea” acestuia, obținem următoarele rezultate:

Următorii pași. Repetăm pasul algoritmului pentru vârfurile rămase. Acestea vor fi vârfurile 6, 4 și 5, conform ordinii.

Finalizarea execuției algoritmului. Algoritmul se termină când nu mai pot fi procesate vârfuri. În acest exemplu, toate nodurile sunt tăiate, dar este o greșeală să presupunem că acesta va fi cazul în orice exemplu - unele vârfuri pot rămâne netălate dacă nu pot fi atinse, adică dacă graficul este deconectat. Rezultatul algoritmului este vizibil în ultima figură: cea mai scurtă cale de la vârful 1 la 2 este 7, la 3 este 9, la 4 este 20, la 5 este 20, la 6 este 11.

Implementarea algoritmului în diferite limbaje de programare:

C++

#include „stdafx.h” #include folosind namespace std; const int V=6; //Algoritmul lui Dijkstra void Dijkstra(int GR[V][V], int st) ( int distanta[V], count, index, i, u, m=st+1; bool vizitat[V]; for (i= 0; "< "<> "; cin>>start; Dijkstra(GR, start-1); system("pause>>void"); )

Pascal

programul DijkstraAlgorithm; foloseste crt; const V=6; inf=100000; tip vector=matrice de întreg; var start: întreg; const GR: matrice de întreg=((0, 1, 4, 0, 2, 0), (0, 0, 0, 9, 0, 0), (4, 0, 0, 7, 0, 0), (0, 9, 7, 0, 0, 2), (0, 0, 0, 0, 0, 8), (0, 0, 0, 0, 0, 0)); (Algoritmul lui Dijkstra) procedura Dijkstra(GR: matrice de întregi; st: întreg); var count, index, i, u, m, min: întreg; distanta: vector; vizitat: matrice de boolean; începe m:=st; pentru i:=1 la V nu începe distanța[i]:=inf; vizitat[i]:=fals; Sfârşit; distanta:=0; pentru count:=1 la V-1, începe min:=inf; pentru i:=1 la V face if (nevizitat[i]) și (distanță[i]<=min) then begin min:=distance[i]; index:=i; end; u:=index; visited[u]:=true; for i:=1 to V do if (not visited[i]) and (GR<>0) și (distanța[u]<>inf) și (distanța[u]+GR inf then writeln(m," > ", i," = ", distance[i]) else writeln(m," > ", i," = ", "ruta indisponibilă"); Sfârşit; (blocul principal al programului) begin clrscr; scrie ("Start vertex >> "); citește(începe); Dijkstra(GR, start); Sfârşit.

Java

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.StringTokenizer; clasă publică Soluție ( private static int INF = Integer.MAX_VALUE / 2; private int n; //numărul de vârfuri din digraf private int m; //numărul de arce din digraful private ArrayList adj; //lista de adiacență privată ArrayList greutate; //greutatea muchiei în digraf boolean privat folosit; //matrice pentru stocarea informațiilor despre nodurile traversate și netraversate private int dist; //matrice pentru stocarea distanței de la vârful de pornire //matrice de strămoși necesară pentru a restabili calea cea mai scurtă de la vârful de pornire private int pred;< n; ++iter) { int v = -1; int distV = INF; //выбираем вершину, кратчайшее расстояние до которого еще не найдено for (int i = 0; i < n; ++i) { if (used[i]) { continue; } if (distV < dist[i]) { continue; } v = i; distV = dist[i]; } //рассматриваем все дуги, исходящие из найденной вершины for (int i = 0; i < adj[v].size(); ++i) { int u = adj[v].get(i); int weightU = weight[v].get(i); //релаксация вершины if (dist[v] + weightU < dist[u]) { dist[u] = dist[v] + weightU; pred[u] = v; } } //помечаем вершину v просмотренной, до нее найдено кратчайшее расстояние used[v] = true; } } //процедура считывания входных данных с консоли private void readData() throws IOException { cin = new BufferedReader(new InputStreamReader(System.in)); cout = new PrintWriter(System.out); tokenizer = new StringTokenizer(cin.readLine()); n = Integer.parseInt(tokenizer.nextToken()); //считываем количество вершин графа m = Integer.parseInt(tokenizer.nextToken()); //считываем количество ребер графа start = Integer.parseInt(tokenizer.nextToken()) - 1; //инициализируем списка смежности графа размерности n adj = new ArrayList[n]; for (int i = 0; i < n; ++i) { adj[i] = new ArrayListint start; // vârful de pornire de la care se caută distanța până la toate celelalte vârfuri private BufferedReader cin;< n; ++i) { weight[i] = new ArrayListprivat PrintWriter cout;< m; ++i) { tokenizer = new StringTokenizer(cin.readLine()); int u = Integer.parseInt(tokenizer.nextToken()); int v = Integer.parseInt(tokenizer.nextToken()); int w = Integer.parseInt(tokenizer.nextToken()); u--; v--; adj[u].add(v); weight[u].add(w); } used = new boolean[n]; Arrays.fill(used, false); pred = new int[n]; Arrays.fill(pred, -1); dist = new int[n]; Arrays.fill(dist, INF); } //процедура восстановления кратчайшего пути по массиву предком void printWay(int v) { if (v == -1) { return; } printWay(pred[v]); cout.print((v + 1) + " "); } //процедура вывода данных в консоль private void printData() throws IOException { for (int v = 0; v < n; ++v) { if (dist[v] != INF) { cout.print(dist[v] + " "); } else { cout.print("-1 "); } } cout.println(); for (int v = 0; v < n; ++v) { cout.print((v + 1) + ": "); if (dist[v] != INF) { printWay(v); } cout.println(); } cin.close(); cout.close(); } private void run() throws IOException { readData(); dejkstra(start); printData(); cin.close(); cout.close(); } public static void main(String args) throws IOException { Solution solution = new Solution(); solution.run(); } }

tokenizer privat StringTokenizer;

//procedura de lansare a algoritmului lui Dijkstra de la vârful de pornire private void dejkstra(int s) ( dist[s] = 0; //cea mai mică distanță până la vârful de pornire este 0 pentru (int iter = 0; iter) (); ) //inițializarea listei care stochează greutățile marginilor weight = new ArrayList[n]; pentru (int i = 0; i<>();<>public Vertex(Nume șir) ( this.name = name; ) private void printPath() ( if (this == this.previous) ( System.out.printf("%s", this.name); ) else if ( this.previous == null) ( System.out.printf("%s(neaccesat)", this.name); ) else ( this.previous.printPath(); System.out.printf(" -> %s( %d)", this.name, this.dist); ) ) public int compareTo(Vertex other) ( return Integer.compare(dist, other.dist); ) ) /** Construiește un grafic dintr-un set de muchii * / public Graph(Edge edges) ( grafic = nou HashMap (muchii.lungime);<>//o trecere pentru a găsi toate nodurile pentru (Edge e: muchii) ( if (!graph.containsKey(e.v1)) graph.put(e.v1, new Vertex(e.v1)); if (!graph. containsKey(e.v2)) graph.put(e.v2, new Vertex(e.v2)) //o altă trecere pentru a seta vârfurile învecinate pentru vecinii (Edge e: edges) ( graph.get(e.v1). put(graph.get(e.v2), e.dist); //graph.get(e.v2).neighbors.put(graph.get(e.v1), e.dist); graph ) ) /** Rulează dijkstra folosind un punct sursă specificat */ public void dijkstra(String startName) ( if (!graph.containsKey(startName)) ( System.err.printf("Graful nu conține vârful de pornire \" %s\"\n", startName return ) final Vertex source = graph.get(startName); q = nou TreeSet ();< v.dist) { // shorter path to neighbour found q.remove(v); v.dist = alternateDist; v.previous = u; q.add(v); } } } } /** Prints a path from the source to the specified vertex */ public void printPath(String endName) { if (!graph.containsKey(endName)) { System.err.printf("Graph doesn"t contain end vertex \"%s\"\n", endName); return; } graph.get(endName).printPath(); System.out.println(); } /** Prints the path from the source to every vertex (output order is not guaranteed) */ public void printAllPaths() { for (Vertex v: graph.values()) { v.printPath(); System.out.println(); } } }

// configurați vârfuri pentru (Vertex v: graph.values()) ( v.previous = v == sursă ? sursă: null; v.dist = v == sursă ? 0: Integer.MAX_VALUE; q.add( v); ) dijkstra(q);

) /** Implementarea algoritmului lui dijkstra folosind un heap binar */ private void dijkstra(final NavigableSet q) ( Vârful u, v; while (!q.isEmpty()) ( u = q.pollFirst(); // vârful cu cea mai scurtă distanță (prima iterație va returna sursa) if (u.dist == Integer.MAX_VALUE) break; q) ( Vârful u, v; while (!q.isEmpty()) ( u = q.pollFirst(); // vârful cu cea mai scurtă distanță (prima iterație va returna sursa) if (u.dist == Integer.MAX_VALUE) break; //#define BIG_EXAMPLE typedef struct node_t node_t, *heap_t; typedef struct edge_t edge_t; struct edge_t ( node_t *nd; /* ținta acestei margini */ edge_t *frate;/* pentru lista legată individual */ int len; /* costul marginii */ ); struct node_t ( edge_t *edge; /* listă de margini conectată individual */ node_t *prin; /* unde nodul anterior se află pe calea cea mai scurtă */ double dist; /* distanță de la nodul de origine */ nume char; /* the, er , nume */ int heap_idx /* link către poziţia heap pentru actualizarea distanţei */ ); /* --- edge management --- */ #ifdef BIG_EXAMPLE # define BLOCK_SIZE (1024 * 32 - 1) #else # define BLOCK_SIZE 15 #endif edge_t *edge_root = 0, *e_next = 0; /* Nu vă deranjează chestiile de gestionare a memoriei, sunt în afară de sens Pretend e_next = malloc(sizeof(edge_t)) */ void add_edge(node_t *a, node_t *b, double d) ( if (e_next == edge_root). ) ( edge_root = malloc(sizeof(edge_t) * (BLOCK_SIZE + 1)); edge_root.sibling = e_next; e_next = edge_root + BLOCK_SIZE; ) --e_next->nd = a->edge; ->edge = e_next; ) void free_edges() ( for (; edge_root; edge_root = e_next) ( e_next = edge_root.sibling; free(edge_root); ) ) /* --- priority queue stuff --- */ heap_t * heap; void set_dist(node_t *nd, node_t *via, double d) ( int i, j; /* știa deja calea mai bună */ if (nd->via && d >= nd->dist) return; /* find intrare heap existentă, sau creați una nouă */ nd->dist = d nd->via = via;< heap->dist; i = j) (heap[i] = heap[j])->heap_idx = i;< heap_len && (j = i * 2) <= heap_len; i = j) { if (j < heap_len && heap[j]->dist > heap->dist) j++;< N_NODES; i++) sprintf(nodes[i].name, "%c", "a" + i); # define E(a, b, c) add_edge(nodes + (a - "a"), nodes + (b - "a"), c) E("a", "b", 7); E("a", "c", 9); E("a", "f", 14); E("b", "c", 10);E("b", "d", 15);E("c", "d", 11); E("c", "f", 2); E("d", "e", 6); E("e", "f", 9); # undef E #else /* BIG_EXAMPLE */ int i, j, c; # define N_NODES 4000 node_t *nodes = calloc(sizeof(node_t), N_NODES); for (i = 0; i < N_NODES; i++) sprintf(nodes[i].name, "%d", i + 1); /* given any pair of nodes, there"s about 50% chance they are not connected; if connected, the cost is randomly chosen between 0 and 49 (inclusive! see output for consequences) */ for (i = 0; i < N_NODES; i++) { for (j = 0; j < N_NODES; j++) { /* majority of runtime is actually spent here */ if (i == j) continue; c = rand() % 100; if (c < 50) continue; add_edge(nodes + i, nodes + j, c - 50); } } #endif heap = calloc(sizeof(heap_t), N_NODES + 1); heap_len = 0; calc_all(nodes); for (i = 0; i < N_NODES; i++) { show_path(nodes + i); putchar("\n"); } #if 0 /* real programmers don"t free memories (they use Fortran) */ free_edges(); free(heap); free(nodes); #endif return 0; }

if (heap[j]->dist >= tmp->dist) break;

(heap[i] = heap[j])->heap_idx = i;< $min) { $min = $dist[$vertex]; $u = $vertex; } } $Q = array_diff($Q, array($u)); if ($dist[$u] == INF or $u == $target) { break; } if (isset($neighbours[$u])) { foreach ($neighbours[$u] as $arr) { $alt = $dist[$u] + $arr["cost"]; if ($alt < $dist[$arr["end"]]) { $dist[$arr["end"]] = $alt; $previous[$arr["end"]] = $u; } } } } $path = array(); $u = $target; while (isset($previous[$u])) { array_unshift($path, $u); $u = $previous[$u]; } array_unshift($path, $u); return $path; } $graph_array = array(array("a", "b", 7), array("a", "c", 9), array("a", "f", 14), array("b", "c", 10), array("b", "d", 15), array("c", "d", 11), array("c", "f", 2), array("d", "e", 6), array("e", "f", 9)); $path = dijkstra($graph_array, "a", "e"); echo "path is: ".implode(", ", $path)."\n";

) heap[i] = tmp;

tmp->heap_idx = i;< dist[v]: # Relax (u,v,a) dist[v] = alt previous[v] = u #pp(previous) s, u = deque(), dest while previous[u]: s.pushleft(u) u = previous[u] s.pushleft(u) return s graph = Graph([("a", "b", 7), ("a", "c", 9), ("a", "f", 14), ("b", "c", 10), ("b", "d", 15), ("c", "d", 11), ("c", "f", 2), ("d", "e", 6), ("e", "f", 9)]) pp(graph.dijkstra("a", "e")) Output: ["a", "c", "d", "e"]

întoarcere nd; ) /* --- Dijkstra chestii; nodurile inaccesibile nu vor intra niciodată în coadă --- */ void calc_all(node_t *start) ( node_t *lead; edge_t *e; set_dist(start, start, 0); while ((lead = pop_queue())) pentru ( e = lead->edge e = e->frate) set_dist(e->nd, lead, lead->dist + e->len ) void show_path(node_t *nd) ( if (nd-> via == nd) ) printf("%s", nd->nume else if (!nd->via) printf("%s(neatins)", nd->name else ( show_path(nd->); via); printf ("-> %s(%g) ", nd->name, nd->dist int main(void) ( #ifndef BIG_EXAMPLE int i; # define N_NODES ("f" - "a" + 1) node_t); *noduri = calloc(sizeof(node_t), N_NODES pentru (i = 0; i

Algoritmul lui Dijkstra rezolvă problema căii celei mai scurte cu un singur vârf pentru un grafic direcționat ponderat G = (V, E) cu vârful sursă s, în care ponderile tuturor muchiilor sunt nenegative ((u, v) ? 0 pentru toate (u) , v) E). În cazul în care marginile graficului nu sunt egale, este recomandabil să folosiți acest algoritm.

Formularea problemei. Există un grafic. Unele dintre vârfurile sale sunt desemnate ca vârf 1. Este necesar să se găsească căile minime de la vârful 1 la fiecare dintre vârfurile graficului. O cale minimă este o cale cu suma minimă a prețurilor de-a lungul căii. Să numim prețul un număr nenegativ care este greutatea marginii.

Ideea algoritmului. Ideea se bazează pe următoarea afirmație evidentă: Să se construiască calea minimă de la vârf O la vârful B. Și să fie conectat vârful B la un anumit număr de vârfuri i. Să notăm cu C i costul drumului de la vârful B la vârful i. Să alegem valoarea minimă din C i. Apoi continuarea minimă a căii din punctul B va trece prin valoarea selectată.

Această afirmație chiar nu necesită dovezi. Și de aici rezultă o consecință foarte gravă. Să existe un set de vârfuri prin care trec deja căi minime. Este garantat existența unei astfel de mulțimi, acesta este vârful 1. Declarația formulată mai sus face posibilă adăugarea unui alt vârf la o mulțime deja existentă de vârfuri (le vom numi în continuare selectate), și deoarece există un număr finit de vârfuri în graficul, apoi într-un număr finit de pași vor fi selectate toate vârfurile graficului și aceasta va fi soluția.

Esența algoritmului lui Dijkstra constă în procedura de a adăuga încă un vârf la setul de cele selectate. Această procedură constă din doi pași:

1. Construim un set de vârfuri incidente celui selectat și găsim printre acestea vârful cu cel mai mic preț. Vârful găsit este adăugat la setul selectat.

2. Construim un set de vârfuri incidente celor selectate și stabilim noi prețuri pentru acestea. Noul preț al unui vârf este prețul minim al căii de la setul de vârfuri selectate la acest vârf. Noul preț este construit astfel:

o. Pentru un vârf neselectat din mulțimea celor selectate, se determină un subset de vârfuri incidente celui dat.

b. Pentru fiecare vârf al submulțimii selectate, se determină costul căii către acesta.

c. Se stabileste pretul minim. Acest preț devine prețul de top.

Algoritmul funcționează cu două tipuri de prețuri: prețul marginii și prețul vârfului. Prețurile coastelor sunt constante. Prețurile vârfurilor sunt constant recalculate. Sensul acestor prețuri este diferit. Costul unei muchii este costul deplasării de la vârf la vârf conectat prin această muchie. Iar prețul vârfului este prețul căii minime. O altă notă importantă se referă la recalcularea prețurilor preliminare. De fapt, are sens să se recalculeze prețurile preliminare numai pentru acele vârfuri care sunt asociate cu vârful adăugat la mulțimea selectată la ultimul pas, deoarece pentru alte vârfuri nu există niciun motiv pentru a modifica prețul preliminar.

Se știe că toate prețurile (de exemplu, de așezare a unei căi sau de călătorie) sunt nenegative. Găsiți cel mai mic cost al căii 1->i pentru tot i=1. n în timp O(n2).

În timpul funcționării algoritmului, unele orașe vor fi evidențiate (la început - doar orașul 1, la sfârșit - toate). În acest caz:

pentru fiecare oraș i selectat, este stocat cel mai mic cost al căii 1->i; Mai mult, se știe că minimul se realizează pe o potecă care trece doar prin orașele selectate;

pentru fiecare oraș i nealocat se stochează cel mai mic cost al căii 1->i, în care doar orașele alocate sunt folosite ca intermediare.

Setul de orașe alocate este extins pe baza următoarei observații: dacă dintre toate orașele nealocate îl luăm pe cel pentru care numărul stocat este minim, atunci acest număr este cel mai mic cost adevărat. Într-adevăr, poate exista o cale mai scurtă. Să ne uităm la primul oraș nemarcat de pe această cale - calea către el este deja mai lungă! (Nenegativitatea prețurilor este esențială aici.)

După ce a adăugat orașul selectat la cele selectate, trebuie să ajustam informațiile stocate pentru orașele neselectate. În acest caz, este suficient să luăm în considerare doar căile în care noul oraș este ultimul punct de transfer, iar acest lucru este ușor de făcut, deoarece știm deja costul minim al căii către noul oraș.

Cu alte cuvinte, fiecărui vârf de la V i se atribuie o etichetă - distanța minimă cunoscută de la acest vârf la a. Algoritmul funcționează pas cu pas - la fiecare pas „vizitează” un vârf și încearcă să reducă etichetele. Algoritmul se termină când toate nodurile au fost vizitate.

Inițializare. Notă superioară o presupus a fi egal 0 , etichetele vârfurilor rămase sunt infinite. Acest lucru reflectă faptul că distanțele de la o la alte vârfuri sunt încă necunoscute. Toate vârfurile graficului sunt marcate ca nevizitate.

Pasul algoritmului. Dacă toate nodurile sunt vizitate, algoritmul se termină. În caz contrar, un vârf este selectat dintre nodurile care nu au fost încă vizitate u, având o etichetă minimă. Avem în vedere tot felul de trasee în care u este penultimul punct. Vârfurile conectate la un vârf u margini, să le numim vecine ale acestui vârf. Pentru fiecare vecin, luați în considerare o nouă lungime de cale egală cu suma etichetei curente uși lungimea marginii de legătură u cu acest vecin. Dacă lungimea rezultată este mai mică decât eticheta vecinului, înlocuiți eticheta cu această lungime. Luând în considerare toți vecinii, marchem vârful u așa cum a fost vizitat și repetați pasul.

Deoarece algoritmul lui Dijkstra alege întotdeauna să proceseze vârfurile cu cel mai mic scor de calea cea mai scurtă, putem spune că este un algoritm lacom.

Să descriem mai detaliat schema de funcționare a algoritmului lui Dijkstra.

Algoritmul folosește trei matrice de N (= numărul de vârfuri ale rețelei) numere fiecare. Prima matrice A conține etichete cu două valori: 0 (vârful nu a fost încă luat în considerare) și 1 (vârful a fost deja luat în considerare); a doua matrice B conține distanțe - cele mai scurte distanțe curente de la vârful corespunzător; a treia matrice c conține numerele de vârfuri - k-lea element C [k] este numărul penultimului vârf de pe calea cea mai scurtă curentă de la Vi la Vk. Matricea distanțelor D specifică lungimea arcului D; dacă nu există un astfel de arc, lui D i se atribuie un număr mare B, egal cu „infinitul mașinii”.

Acum putem descrie:

1. (inițializare). Într-o buclă de la 1 la N, umpleți tabloul A cu zerouri; umpleți tabloul C cu numărul i; mutați al-lea rând al matricei D în tabloul B, A [i]: =1; C [i]: =0 (i este numărul vârfului de pornire)

2. (treaptă generală). Aflați minimul dintre cele nemarcate (adică acele k pentru care A [k] =0); să fie atins minimul la indicele j, adică. B[j]<=B [k] Затем выполняются следующие операции: A [j]: =1; если B [k] >B [j] +D , apoi (B [k]: =B [j] +D ; C [k]: =j) (Condiția înseamnă că calea Vi. Vk este mai lungă decât calea Vi. Vj Vk) . (Dacă toate A [k] sunt marcate, atunci lungimea căii de la Vi la Vk este egală cu B [k]. Acum trebuie să) enumerați vârfurile incluse în calea cea mai scurtă).

3. (oferirea unui răspuns). (Calea de la Vi la Vk este dată în ordine inversă prin următoarea procedură:)

2. Problema z;

3. z: =C [z]. Dacă z = O, atunci sfârșitul, în caz contrar, treceți la 3.2.

Pentru a executa algoritmul, trebuie să căutați prin matricea B de N elemente de N ori, adică. Algoritmul lui Dijkstra are complexitate pătratică: O(n2).

Mai jos este o diagramă bloc a algoritmului lui Dijkstra (vezi Fig. 2).

Fig.2. Organigrama algoritmului lui Dijkstra

La începutul algoritmului, distanța pentru vârful inițial este setată la zero și toate celelalte distanțe sunt umplute cu un număr pozitiv mare (mai mare decât calea maximă posibilă din grafic). Matricea flags este umplută cu zerouri. Apoi începe bucla principală.

La fiecare pas al buclei, căutăm un vârf cu o distanță minimă și un steag egal cu zero. Apoi îi setăm pavilionul la 1 și verificăm toate vârfurile adiacente. Dacă distanța din ea este mai mare decât suma distanței până la vârful curent și lungimea muchiei, atunci o reducem. Bucla se termină când steagurile tuturor vârfurilor devin egale cu 1.

Dat un grafic ponderat direcționat sau nedirecționat cu vârfuri și muchii. Greutățile tuturor marginilor nu sunt negative. Este indicat un anumit vârf de început. Trebuie să găsim lungimile celor mai scurte căi de la un vârf la toate celelalte vârfuri și, de asemenea, să oferim o modalitate de a afișa în sine cele mai scurte căi.

Această problemă se numește problema căilor cele mai scurte cu o singură sursă.

Algoritm

Iată un algoritm care a fost propus de un cercetător olandez. Dijkstra(Dijkstra) în 1959

Să creăm o matrice în care pentru fiecare vârf vom stoca lungimea curentă a celei mai scurte căi de la până la . Inițial, și pentru toate celelalte vârfuri, această lungime este egală cu infinitul (atunci când este implementată pe un computer, de obicei, un număr suficient de mare este ales ca infinit, evident mai mare decât lungimea posibilă a căii):

În plus, pentru fiecare vârf vom stoca dacă este sau nu marcat încă, adică. Să creăm o matrice booleană. Inițial, toate nodurile nu sunt marcate, adică.

Algoritmul lui Dijkstra în sine constă din iterații. La următoarea iterație, este selectat vârful cu cea mai mică valoare dintre cele nemarcate încă, adică:

(Este clar că la prima iterație va fi selectat vârful de pornire.)

Vârful selectat în acest fel este marcat. Mai departe, la iterația curentă, de la vârf relaxare: Toate muchiile care emană dintr-un vârf sunt examinate, iar pentru fiecare astfel de vârf algoritmul încearcă să îmbunătățească valoarea. Fie lungimea muchiei curente egală cu , apoi sub formă de cod relaxarea arată astfel:

Aceasta încheie iterația curentă, algoritmul trece la următoarea iterație (se selectează din nou vârful cu cea mai mică valoare, se fac relaxări din acesta etc.). În acest caz, în final, după iterații, toate vârfurile graficului vor deveni marcate, iar algoritmul își finalizează munca. Se afirmă că valorile găsite sunt lungimile necesare ale celor mai scurte căi de la la .

Este demn de remarcat faptul că, dacă nu toate vârfurile graficului sunt accesibile de la vârf, atunci valorile lor vor rămâne infinite. Este clar că ultimele câteva iterații ale algoritmului vor selecta doar aceste vârfuri, dar aceste iterații nu vor produce nicio muncă utilă (deoarece o distanță infinită nu va putea relaxa alte distanțe, chiar infinite). Prin urmare, algoritmul poate fi oprit imediat de îndată ce un vârf cu o distanță infinită este luat ca vârf selectat.

Refacerea căilor. Desigur, de obicei trebuie să cunoașteți nu numai lungimile celor mai scurte căi, ci și să obțineți căile în sine. Vom arăta cum să stocăm informații suficiente pentru reconstrucția ulterioară a drumului cel mai scurt de la orice vârf. Pentru aceasta, așa-numitul serie de strămoși: o matrice în care, pentru fiecare vârf, este stocat numărul vârfului care este penultimul în calea cea mai scurtă către vârf. Acest lucru folosește faptul că, dacă luăm calea cea mai scurtă către un vârf și apoi eliminăm ultimul vârf din această cale, vom obține o cale care se termină la un vârf, iar această cale va fi cea mai scurtă pentru vârf. Deci, dacă avem această matrice de strămoși, atunci cea mai scurtă cale poate fi restabilită din ea, pur și simplu luând strămoșul din vârful curent de fiecare dată până când ajungem la vârful de pornire - în acest fel vom obține calea cea mai scurtă dorită, dar scrisă în ordine inversă. Deci, cea mai scurtă cale către vârf este:

Rămâne să înțelegem cum să construim această serie de strămoși. Cu toate acestea, acest lucru se face foarte simplu: cu fiecare relaxare reușită, de exemplu. când de la un vârf selectat există o îmbunătățire a distanței până la un vârf, scriem că strămoșul vârfului este vârf:

Dovada

Declarația principală, pe care se bazează corectitudinea algoritmului lui Dijkstra, este următorul. Se afirmă că, după ce orice vârf devine marcat, distanța actuală până la acesta este deja cea mai scurtă și, în consecință, nu se va mai schimba.

Dovada Vom produce prin inducție. Pentru prima iterație, validitatea sa este evidentă - pentru vârful avem , care este lungimea celei mai scurte căi către acesta. Să fie acum această afirmație adevărată pentru toate iterațiile anterioare, de exemplu. toate nodurile deja marcate; Să demonstrăm că nu este încălcat după finalizarea iterației curente. Fie vârful selectat la iterația curentă, adică. vârful pe care algoritmul îl va eticheta. Să demonstrăm că este într-adevăr egală cu lungimea drumului cel mai scurt către ea (notăm această lungime cu ).

Luați în considerare calea cea mai scurtă către vârf. Este clar că această cale poate fi împărțită în două căi: constând numai din vârfuri marcate (cel puțin vârful de pornire va fi în acest drum) și restul căii (poate include și vârfuri marcate, dar trebuie să înceapă cu unul nemarcat). Să notăm cu primul vârf al căii și cu ultimul vârf al căii.

Să demonstrăm mai întâi afirmația noastră pentru vârf, i.e. hai sa dovedim egalitatea. Cu toate acestea, acest lucru este aproape evident: la urma urmei, într-una dintre iterațiile anterioare am selectat un vârf și am efectuat relaxarea din acesta. Deoarece (în virtutea alegerii vârfului) cea mai scurtă cale către este egală cu cea mai scurtă cale către plus muchia, atunci când vă relaxați de la, valoarea va fi setată de fapt la valoarea necesară.

Datorită nenegativității costurilor marginii, lungimea căii celei mai scurte (și după ce tocmai s-a dovedit, este egală cu ) nu depășește lungimea căii celei mai scurte până la vârf . Având în vedere că (la urma urmei, algoritmul lui Dijkstra nu a putut găsi o cale mai scurtă decât este posibilă în general), obținem în cele din urmă următoarele relații:

Pe de altă parte, deoarece ambele și sunt vârfuri neetichetate, atunci deoarece la iterația curentă a fost ales vârful, și nu vârful, obținem o altă inegalitate:

Din aceste două inegalități concluzionăm egalitatea , iar apoi din relațiile găsite anterior obținem:

Q.E.D.

Implementarea

Deci, algoritmul lui Dijkstra constă din iterații, în fiecare dintre care este selectat vârful neetichetat cu cea mai mică valoare, acel vârf este marcat și apoi sunt examinate toate muchiile care emană din acel vârf, iar de-a lungul fiecărei muchii se încearcă îmbunătățirea valoare la celălalt capăt al muchiei.

Timpul de rulare al algoritmului este format din:

Cu cea mai simplă implementare a acestor operații, căutarea unui vârf va necesita operații, iar o relaxare va necesita operații, iar finalul asimptotice algoritmul este:

Implementarea:

const int INF = 1000000000 ;< vector < pair< int ,int >int main() ( int n; ... citește n ... vector > > g (n);...citirea graficului... int s = ...;< int >// vârful de pornire< char >vector< n; ++ i) { int v = - 1 ; for (int j= 0 ; j< n; ++ j) if (! u[ j] && (v == - 1 || d[ j] < d[ v] ) ) v = j; if (d[ v] == INF) break ; u[ v] = true ; for (size_t j= 0 ; j< g[ v] .size () ; ++ j) { int to = g[ v] [ j] .first , len = g[ v] [ j] .second ; if (d[ v] + len < d[ to] ) { d[ to] = d[ v] + len; p[ to] = v; } } } }

d(n, INF), p(n);

d[ s] = 0;

1.2 Descrierea matematică a algoritmului

Fie dat un grafic G = (V, E) cu ponderile muchiilor f(e) și un vârf de sursă selectat u. Să notăm cu d(v) distanța cea mai scurtă de la sursa u până la vârful v.

Fie că toate distanțele care nu depășesc un anumit număr r au fost deja calculate, adică distanțele până la vârfuri din mulțime V_r = $ v \in V \mid d(v) \le r $. Lasă

(v, w) \in \arg\min $ d(v) + f(e) \mid v \in V, e = (v, w) \in E $.

Apoi d(w) = d(v) + f(e), iar v se află pe calea cea mai scurtă de la u la w.

Cantitati d^+(w) = d(v) + f(e), unde v \in V_r , e = (v, w) \in E , sunt numite distante estimateși sunt o estimare superioară pentru distanțe reale: d(w) \le d^+(w) .

La fiecare pas, algoritmul lui Dijkstra găsește vârful cu cea mai mică distanță estimată, îl marchează ca vizitat și actualizează distanțele estimate pentru toate capetele marginilor care provin din acesta.

1.3 Miezul de calcul al algoritmului

Calculele de bază implică operații pe o coadă prioritară:

extrage elementul minim (delete_min);
scăderea priorității unui element (decrease_key).

1.4 Macrostructura algoritmului

Pseudocod algoritm:

Date de intrare: grafic cu vârfuri V, coaste E cu solzi f(e); u. vârful sursă Imprima : distante(d v d ∈ V) la fiecare vârf u. de sus := Q nou coada de prioritate d ∈ V: pentru fiecare d = u dacă : distante(d) := 0 apoi : distante(d) := ∞ de sus altfel d, : distante(d)) .introduce( de sus ≠ ∅: d := de susîn timp ce coada de prioritate e = (d, .delete_min()) ∈ E: pentru fiecare : distante(.delete_min()) > : distante(d) + f(e): : distante(.delete_min()) := : distante(d) + f(e) de sus w .delete_min(), : distante(.delete_min()))

.decrease_key(

1.5 Schema de implementare a algoritmului secvenţial

Implementarea specifică a algoritmului lui Dijkstra este determinată de alegerea algoritmului de așteptare cu prioritate utilizat. În cel mai simplu caz, poate fi o matrice sau o listă, căutarea minimului în care necesită scanarea tuturor nodurilor. Este mai eficient să folosiți grămada; Cea mai cunoscută estimare a complexității este folosirea unui morman Fibonacci.

O posibilă opțiune de implementare este atunci când vârfurile sunt adăugate la coadă nu în etapa de inițializare, ci în momentul primei vizite.

1.6 Complexitatea secvenţială a algoritmului

Complexitatea secvenţială a algoritmului este O(C_1 m + C_2n) , unde
C_1 – numărul de operații pentru reducerea distanței până la vârf;

C_2 – numărul de operații pentru calcularea minimului.

Algoritmul original al lui Dijkstra a folosit liste ca structură internă de date, pentru care C_1 = O(1) , C_2 = O(n) , deci complexitatea totală a fost O(n^2) .

1.7 Graficul de informare

Un grafic de algoritm este dat pentru o implementare de bază a algoritmului lui Dijkstra pe liste sau tablouri.

Figura 1. Graficul algoritmului fără afișarea datelor de intrare și de ieșire. n=3. Galben indică operațiuni de comparare, verde indică operațiuni de schimbare a etichetelor vârfurilor, iar albastrul indică etichetarea vârfurilor.

1.8 Resursa de paralelism al algoritmului

Algoritmul lui Dijkstra permite o paralelizare eficientă, timpul mediu de rulare este O(n^(1/3)\ln n) cu cantitatea de calcul O(n\ln n + m) .

Prima estimare se bazează pe caracteristica daps, care estimează numărul de accesări la memorie (citiri și scrieri) efectuate pe secundă. Această caracteristică este un analog al estimării flops în legătură cu lucrul cu memoria și este mai mult o evaluare a performanței interacțiunii cu memoria decât o evaluare a localității. Cu toate acestea, servește ca o sursă bună de informații, inclusiv compararea cu rezultatele pentru următoarea caracteristică cvg.

Figura 6 prezintă valorile daps pentru implementările algoritmilor obișnuiți, sortate în ordine crescătoare (cu cât sunt mai mari daps, cu atât performanța este în general mai mare). Puteți vedea că performanța memoriei este destul de scăzută. Acest lucru nu este surprinzător, deoarece implementările de algoritmi peste grafice au aproape întotdeauna o eficiență scăzută din cauza accesului neregulat la date, lucru pe care l-am văzut când am analizat profilul solicitărilor.

Figura 6. Comparația valorilor scorului daps

A doua caracteristică, cvg, este menită să ofere o estimare a localității mai independentă de mașină. Acesta determină cât de des trebuie programul să extragă date în memoria cache. În consecință, cu cât valoarea cvg este mai mică, cu atât mai rar trebuie făcut acest lucru, cu atât localitatea este mai bună.

Figura 7 prezintă valorile cvg pentru același set de implementări, sortate în ordine descrescătoare (cu cât este mai mic cvg, cu atât localitatea în general este mai mare). Se poate observa că în acest caz valoarea cvg se corelează bine cu scorul de performanță și reflectă localitatea scăzută, ceea ce este în concordanță cu concluziile desprinse din evaluarea calitativă a localității.

Figura 7. Comparația valorilor scorului cvg

2.3 Metode și caracteristici posibile de implementare paralelă a algoritmului

2.4 Scalabilitate a algoritmului și implementarea acestuia

2.4.1 Scalabilitatea algoritmului

2.4.2 Scalabilitatea implementării algoritmului

Să realizăm un studiu al scalabilității implementării paralele a algoritmului conform metodologiei. Cercetarea a fost efectuată pe supercomputerul Lomonosov al Complexului de Supercomputer al Universității din Moscova. Setul și limitele valorilor parametrilor modificabili pentru lansarea implementării algoritmului:

numărul de procesoare cu valori întregi pătrate;
dimensiunea graficului în trepte de 16000.

Următoarea figură prezintă un grafic al performanței implementării selectate a algoritmului în funcție de parametrii variabili de lansare.

Figura 8. Implementarea în paralel a algoritmului. Performanța se modifică în funcție de numărul de procesoare și de dimensiunea zonei.

Datorită particularităților implementării paralele a algoritmului, performanța în ansamblu este destul de scăzută și crește lent pe măsură ce numărul de procese crește, iar când se apropie de numărul de procese 128, acesta începe să scadă. Acest lucru se explică prin utilizarea operațiilor colective la fiecare iterație a algoritmului și prin faptul că costurile schimburilor de comunicații cresc semnificativ odată cu creșterea numărului de procese utilizate. Calculele pe fiecare proces sunt destul de rapide și, prin urmare, descompunerea graficului compensează slab efectul costurilor schimburilor de comunicații.

2.5 Caracteristicile dinamice și eficiența implementării algoritmului

Pentru a efectua experimentele, a fost folosită o implementare a algoritmului lui Dijkstra. Toate rezultatele au fost obținute pe supercalculatorul Lomonosov. Au fost folosite procesoare Intel Xeon X5570 cu performanțe de vârf de 94 Gflops, precum și compilatorul Intel 13.1.0. Cifrele arată eficiența implementării algoritmului lui Dijkstra pe 32 de procese.

Figura 9. Graficul de încărcare a CPU la executarea algoritmului lui Dijkstra

Graficul de încărcare a procesorului arată că aproape tot timpul rulează programul, nivelul de încărcare este de aproximativ 50%. Acest lucru indică o încărcare uniformă a procesoarelor cu calcule, folosind 8 procese per nod de calcul și fără a utiliza Hyper Threading.

Figura 10. Graficul operațiilor cu virgulă mobilă pe secundă la executarea algoritmului lui Dijkstra

Figura 10 prezintă un grafic al numărului de operații în virgulă mobilă pe secundă. Graficul arată o performanță generală foarte scăzută de calcul de aproximativ 250 Kflops la vârf și aproximativ 150 Kflops în medie pe toate nodurile. Acest lucru indică faptul că aproape toate calculele din program sunt efectuate cu numere întregi.

Graficul scrierilor de memorie arată o imagine similară a neuniformității computaționale, în care doar câteva procese scriu activ în același timp. Acest lucru se corelează cu alte programe de execuție. Este demn de remarcat numărul destul de scăzut de accesări la scriere în memorie. Acest lucru indică o bună organizare a calculelor și o gestionare destul de eficientă a memoriei.

Figura 15. Graficul vitezei de transmisie prin rețeaua Infiniband în octeți/sec când se execută algoritmul lui Dijkstra

Graficul vitezei de transfer de date a rețelei Infiniband arată o rată de transfer de date destul de ridicată în octeți pe secundă. Acest lucru sugerează că procesele schimbă intens între ele și, probabil, bucăți destul de mici de date, deoarece performanța de calcul este ridicată. Este de remarcat faptul că viteza de transfer variază între procese, indicând un dezechilibru de calcul.

Figura 16. Graficul vitezei de transmisie prin rețeaua Infiniband în pachete/sec atunci când algoritmul lui Dijkstra rulează

Graficul ratei de transfer de date în pachete pe secundă arată rate de transfer de date extrem de mari. Acest lucru sugerează că procesele schimbă probabil cantități nu foarte semnificative de date, dar foarte intens. Operațiunile colective sunt folosite la fiecare pas cu bucăți mici de date, ceea ce explică această imagine. Există, de asemenea, mai puțin dezechilibru între procese decât se vede în graficele de memorie, calcul și octeți/sec. Acest lucru indică faptul că procesele schimbă același număr de pachete conform algoritmului, dar primesc cantități diferite de date și efectuează calcule inegale.

Figura 17. Graficul numărului de procese care așteaptă să intre în etapa de numărare (Loadavg) când algoritmul lui Dijkstra rulează

Graficul numărului de procese care așteaptă să intre în etapa de calcul (Loadavg) arată că pe toată durata funcționării programului, valoarea acestui parametru este constantă și aproximativ egală cu 8. Aceasta indică funcționarea stabilă a programului cu toate nodurile încărcate. cu calcule. Acest lucru indică o încărcare foarte rațională și statică a resurselor hardware de către procese. Și arată o eficiență destul de bună a implementării în curs de realizare. În general, conform monitorizării sistemului a programului, putem concluziona că programul a funcționat destul de eficient și stabil. Utilizarea memoriei este foarte intensă, iar utilizarea mijloacelor de comunicare este extrem de intensivă, dar volumele de date transferate nu sunt mari. Acest lucru indică latența solicitantă a mediului de comunicare a părții algoritmice a programului. Eficiența scăzută pare să se datoreze volumului destul de mare de transferuri pe proces și schimburilor intensive de mesaje.