Grade 11 · 6 algorithmsCitește în română

Directed graphs and shortest pathsGrafuri orientate și drumuri minime

Every directed graphs and shortest paths algorithm from the Romanian high school curriculum, with the idea explained, its complexity, examples and code you can edit and run right here.

Create a free account Browse the collection

6algorithms
7chapters
1grade

Directed graphs and shortest paths

Grafuri orientate și drumuri minime · 6 algorithms

Strongly connected componentsComponentele tare conexeA directed graph is strongly connected if for any two nodes x and y there is a path from x to y and a path from y to x. A strongly connected…O(n³)
Shortest paths from one node (Dijkstra's algorithm)Drumuri minime de la un nod (algoritmul lui Dijkstra)We want the minimum cost of the path from node s to every other node, when all arc costs are non-negative. d[s] = 0, the rest 'infinity'. At every…O(n²)
In-degrees and out-degreesGradele interne și externeIn a directed graph the edges have a direction and are called arcs: the arc (x, y) leaves x and enters y. The out-degree d+(x) is the number of arcs…O(n)
Reachability matrix (Roy-Warshall algorithm)Matricea drumurilor (algoritmul Roy-Warshall)The reachability matrix has d[i][j] = 1 if there is a path (of length at least 1) from i to j and 0 otherwise. We start from the adjacency matrix.…O(n³)
Shortest paths between all pairs of nodes (Roy-Floyd)Drumuri minime între toate perechile de noduri (Roy-Floyd)Every arc (x, y) has a cost c ≥ 0. The cost matrix d starts with d[i][i] = 0, d[x][y] = the arc's cost and 'infinity' where there is no arc. For…O(n³)
Topological sortSortarea topologicăThe arc (x, y) means 'x must be done before y'. A topological sort is an order of all nodes in which every arc goes from left to right; it exists…O(n²)