An optimal algorithm
to find the shortest path in the graph
Introduction:
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