What White Means On Facebook Chat

DIJKSTRA ALGORITHM

Dijkstra's algorithm, also called shortest path algorithm is an algorithm for determining the shortest path given a source vertex to other vertices in a directed graph with weights in each edge. Its name refers to Edsger Dijkstra, who first described it in 1959.

ALGORITHM Given a weighted directed graph of N nodes are not isolated , x is the initial node, a vector D of size N stored at the end of the algorithm the distances from x to all other nodes.

1. Initialize all distances in D with an infinite value on because they are unknown at first, except of x to be placed at 0 because the distance from x to x would be 0.
2. Let a = x (we take as the current node).
3. We travel all the adjacent nodes, except nodes marked, call these vi.
4. If the distance from x to vi stored in D is greater than the distance from x to a plus the distance from a to vi, this is replaced with the second named, ie
if (Di> Da + d (a, vi)) then Di = Da + d (a, vi)
5. We mark the node as complete a.
6. We as the next current node with the lowest D value (can be done by storing the values \u200b\u200bin a priority queue) and go back to step 3 while there are unmarked nodes. Once completed
the algorithm, D is completely full.

For what is useful?

often in everyday life we \u200b\u200bfind the most efficient way to reach our destination, this algorithm is perfect, as it evaluates all possible paths and choose the shortest to the destination. Thereby reducing the most efficient route. Now compared to my career is really useful, since making a program that solves the problem in the shortest time is the best. Putting it another way, you'll be hired, not.

Calculate the shortest path from "1" to any node