Sorting nodes of a graph

First , in order to perform this function properly, you need to understand that graphs should be directed and acyclic.

Determine the "in degree of each vertex".

There shouldnt be any cycle inside the graph.

First, we need to define the key concept of this algorithm : indegree.

The indegree of a node represents the number of parent nodes.



Quicksort ls a powerful sorting algorithm

Here is how it works :

Select arbitrarily a pivot X from an array

Insert on the right of X, any serie of element being smaller than it (keeping the same order, as the original array). On the left, perform the same operation with bigger elements.

Ex :

X = 4

Arr = [ 2 1 3 6 5 4 ];

NewArr =[ 2 1 3 4 6 5]

Now, consider the obtention of such an array :

B= bigger elements array
Y = smaller elements array

[B, X , Y];

Perform recursively the same operation on both arrays , which will finally return such an array :

[sortedX , pivot , sortedY];



Dijsktra is a single source shortest path algorithm.

Here are basically how to perform this algorithm :

Dijskstra algorithm follows a greedy method (following a step by step procedure, to arrive to an optimal solution).

It works on directed, and undirected graphs.

It uses the same relaxation method as bellman Ford

(if vA + wAB < vB){

vB = vA +wAB

vA parent of vB


We first relax the adjacent nodes to the source. All the other vertexes are set to. “+infinity".

Then, start by choosing the smallest unvisited vertex value. Relax (if possible) all the adjacent nodes.

Repeat the step : visit the smallest unvisited vertex value, and perform, if possible, relaxation to adjacent edges.

When there are no unvisited vertexes anymore, the execution of the algorithm is done.