Search This Blog

Simplicity is the ultimate sophistication.” — Leonardo da Vinci
Contact me:

Monday, 27 July 2015

An optimal algorithm for the shortest path in the graph

An optimal algorithm to find the shortest path in the graph

Many real-life solutions rely on shortest path algorithms, especially games rely on them! If a graphic game character traces your moves along a complicated path and finds you, then it is obvious that the game implemented a graph algorithm to find the shortest path to approach you. Is it really that easy to find an optimal path to reach a point in a graph? No not exactly, as the upper bound of the Dijkstra’s algorithm is $O(|V|^2)$. If we assume your game map to be a big grid, then the number of cells in the grid is equal to the number $|V|$. But this is still the worst case, and for most times we don’t need to consider the worst case. Let me describe the Dijkstra’s algorithm. 

For any set of nodes with weighed connections among them the shortest path can be computed in the following way:
1.  Let the set $V$ contain the list of all the possible nodes constituting the graph.

2. Now let $E$ be the set of all the possible connections between any two vertices.

3. If $|V|$ denotes the magnitude or the number of elements in the set $V$, then the maximum number of possible edges (interconnections between two vertices) can be written as $\frac{|V|^2 - |V|}{2}$, which is the expression stating the sum of natural numbers from $1$ to $|V|$.

4. Let the start point be $a\in V$, and the end point be $b \in V$.

5. Let’s represent the neighbors of $a$ as $N(a)$, where $N = \{x, y : x \in V, y\subseteq V \} $.

6. Now we may further define another relation $Dis(a, b), b\in N(a)$ which shows the distance between the points $a$ and $b$.

7. For all nodes $b\in N(a)$ set the distance between $a$ to $b$ in the node $b$, such that in the future, the distance value is accessible from $b$ itself. Now mark the node $a$ as “seen”. This is done to avoid the iteration process from checking this node again.

8. Now for each node $c\in N(b)$ obtain the distance from $b$ to $c$ and sum it up with the distance value recorded in $b$ and set it to the node $c$ such that it is visible when referred to the node $c$. Here $b$ takes the place of $a$ and $c$ takes the place of $b$. In this case, there are links that head back to the previous node. Since the previous node, which is $a$ had been marked “seen” the algorithm does not go back to $a$. There is a possibility that the program reaches a node that already has a distance label on it. In this case, the algorithm checks if the value recorded is greater than the newer value that was going to be recorded. If it was greater, then that value will be replaced by the newer value. If it was not greater, then no modification is done to it.

9. Now each node that’s reached is marked “seen” before proceeding with the algorithm. Again this ensures that the algorithm does not reach that node again.

10. This process continues until the destination node is reached.

11. As these distances are recorded, the shortest path is also recorded. It is not necessary to record the path explicitly. One way to obtain the path from these recorded distance is to transverse back the origin node from the destination node by choosing the node with the smallest value each time.

The above algorithm runs at $O(|V|^2)$; this is because, when there is a situation such that each node is checked before reaching the destination node, and if each node it connected to each other node, then it is obvious that the algorithm had checked through each of the edges before reaching the destination. So, why do we count edges here? The answer is simple, once the vertices in $b$ get marked starting from $a$ the algorithm checks all the paths that are connected to $b$ before choosing the node it must reach. So in this case, the algorithm visits through all the possible edges, and at times when more than one edge leads to a particular node, the shortest one is retained with the longer one being ignored.

Let me prove that $|E| = \frac{|V|^2 - |V|}{2}$ if all nodes are connected to each other node. We consider each node to be connected to each other node because, that’s the only possible way to allot the maximum possible connections. Let $a_1\in V$ be connected to another node $a_2\in V$. So once we say that $a_1$ and $a_2$ are connected, it is obvious that the connection $a_2$ to $a_1$ also exists. So $a_1$ would establish $|V| - 1$ connections (as all the nodes other than $a_1$ gets connected). Now $a_2$ is made to connect with ever other node it isn’t connected with. From the previous step, $a_1$ is connected to $a_2$ so leaving $a_1$, $a_2$will have to connect with $(|V| - 1) - 1$ nodes (which includes $a_3, a_4 … $). So Now while forming the connection for $a_3$ with every other node, we would be making $((|V| - 1) -1)- 1$ connections (after ignoring $a_1$, $a_2$ and $a_3$).  So for the node $a_n$, we would be making $|V| - n$ connections, which is obviously zero.
Now summing up all the connections we made, we get: $\sum\limits_{i=1}^{n=|V|}{|V| - i} = \frac{|V|^2 - |V|}{2}$.
A tree:

This is a special kind of a graph. A tree contains numerous branches and leaves at it ends. A tree in “data structures” is a kind of structuring of data that more or less imitates the structure of any ordinary tree. The origin of a tree is the root. So we have a “root node” from which all the other nodes are branched.

The above diagram represents a binary tree. Each node in the tree other than $1$ have a parent node. The node $1$ is the parent node for $2$ and $3$ and the node $2$ is the parent node for $4$ and $5$. As we descend by one level each time, the number of nodes in that level increases exponentially.

 Here, by level I mean the number of nodes it takes to transverse back to reach the node $1$. $1$ is the first level and $2$ and $3$ are the second level nodes with $4, 5, 6, 7$ as the third level nodes. So for a binary tree with $n$ levels, the number of nodes present in the $n$th level is $N_b(n) = 2^{n-1} $. The $-1$ in the exponent signifies that the value of $n$ starts with one, with node $1$ being the root node, and the nodes $2, 3$ which fall under the “second level”; and as there are two second level nodes, we have $2^{2 – 1} = 2$.   

So how do we find the total number of nodes of a binary tree with $n$ nodes? We may find this by summing up the number of nodes for each level. This can be expressed as $S_n = \sum \limits_{i=0}^n 2^n $. This is an example of geometric progression. A geometrically progressive series can be computed by equating the difference of the sum $S$ times $2$ and $S$ to the difference between $2^0$ and $2^{n+1}$.

copyright © 2015 K Sreram, All rights reserved

No comments:

Post a Comment

Featured post

Why complicating matters is not good

“ Simplicity is the ultimate sophistication.” — Leonardo da Vinci Why is complicating things wrong ? - K Sr...