Simulation
of Bellman's Algorithm
contributed
by Madhusudhan N
Simulation of Bellman
Ford Routing algorithm with
7 nodes.
Possible node Routing Diagrams
Step 1 : red arrows point to
nodes reachable (immeidate neighbour)
within 1 hop from the inspected
node (Blue node). The distance
from the start node to: b=1,
c=1, e=1, f=1. Node b has the
minimum distance. Any other
path to b visits another red
node, and will be longer than
1. Node b will be colored orange
to indicate 1 is the length
of the shortest path to b.
Step 2: Red arrows point to
neighbour nodes that reachable
from neighbour of inspected
node that already have a final
distance. The distance to: c=1,
e=1, f=1. Node c has the minimum
distance. There are no other
arrows coming in to c. Node
c will be colored orange to
indicate 1 is the length of
the shortest path to c.
Step 3: Red arrows point to
neighbour nodes that reachable
from neighbour of inspected
node that already have a final
distance. The distance to: e=1,
f=1. Node e has the minimum
distance. There are no other
arrows coming in to e. Node
e will be colored orange to
indicate 1 is the length of
the shortest path to e.
Step 4: Red arrows point to
neighbour nodes that reachable
from neighbour of inspected
node that already have a final
distance. The distance to: f=1.
Since this node forms a 'bridge'
to the remaining nodes, all
other paths to this node will
be longer. Node f will be colored
orange to indicate 1 is the
length of the shortest path
to f.
Step 5: Red arrows point to
neighbour nodes that reachable
from neighbour of inspected
node that already have a final
distance. The distance to: d=2,
g=2. Node d has the minimum
distance. Any other path to
d visits another red node, and
will be longer than 2.
Node d will be colored orange
to indicate 2 is the length
of the shortest path to d.
Step 6: Red arrows point to
neighbour nodes that reachable
from neighbour of inspected
node that already have a final
distance. The distance to: g=2.
There are no other arrows coming
in to g. Node g will be colored
orange to indicate 2 is the
length of the shortest path
to g.
Final Step: Follow the RED
path from the start node to
get the shortest path to the
destination node. The length
of the path is written in node.
DV is given in Table.
| |
A |
B |
C |
D |
E |
F |
G |
A |
- |
1B |
1C |
2F |
1E |
1F |
2F |
B |
1A |
- |
1C |
3B |
2B |
2B |
3B
|
C |
1A |
1B |
-
|
3C |
2C |
2C |
3C
|
D |
2F |
3F |
3F |
- |
3F |
1F |
2F |
E |
1A |
2E
|
2E |
3E |
-
|
2E |
3E
|
F |
1A |
2F |
2F |
1D |
2F |
-
|
2D
|
G |
2F |
4D |
4D |
2F |
4D |
2D |
-
|
-------------------------------------------------------------------------------
Simulation using JAVA Applet:
***, ###
Source code of applet html
file:***, ###
<HTML>
<HEAD>
<TITLE>Simulation of Algorithm</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<p align="center"><font
color="#0000CC">Bellman's
Algorithm Simulator </font></p>
<hr width="100%"
color="#FF3366">
<p><applet code="bellmanFord.class"
width="793" height="584">
</applet></p>
<hr width="100%"
color="#FF3366">
<div align="center"><font
color="#0000CC">Peary
and Justin 11/20/2001</font>
</div>
<p> </p>
</BODY>
</HTML>
The JAVA program files: (you
have to compile this source
of .java files and than put
all class files in the same
folder as the above html file
is)
1.
BellmanFord.java
2.
DocOptions.java
3. DocText.java
4. Documentation.java
5. GraphCanvas.java
6. Options.java
7. RouteTable.java
Applet Instructions
The Applet explains the Bellman's
Algorithm to find the shortest
path between various nodes in
the network.
The startnode is blue, other
nodes are grey. The first node
you draw on the screen will
be the startnode.
Draw a node by click ing the
mouse. To draw an arrow click
mouse in a node and drag it
to another node.
Draw a node by clicking the
mouse.
To remove a node press <ctrl>
and click on the node.
To move a node press <shift>,
click on the node and drag it
to its new position.
To change the weight of an arrow,
click on the arrowhead and drag
it along the arrow.
To remove an arrow, change its
wight to 0.
Applet Commands
Clear Button: remove the current
graph from the screen.
Reset Button: remove the results
of the algorithm from the graph
and unlock screen.
Run Button: run the algorithm
on the graph.
Step Button: An opportunity
to step through the algorithm.
Example List: displays three
example graphs on the screen
for you.
Applet Features
The graph that is used to represent
to network is the directed graph
(for adjusting weight purpose).
Therefore to run the algorithm
correctly, it requires two links
between any two nodes.
This applet can be supported
the graph up to 7 nodes (due
to table size).
There are 5 examples provided
in the applet.
When change any weight in the
graph, press reset to update
the table.
***basic algorithm is based
on a A Dijkstra's Shortest Path
Alorithm Animation in Java written
by Carla Laffra at PACE Univeristy
in New York. (link)
### : The applet is created
by Parry and Justine as a part
of project: "Applet for
Bellmanford (RIP) and Dijkstra
(OSPF)"
