From: Bob Sinclair (bsinclair@netmasterclass.net)
Date: Thu Jul 08 2004 - 19:01:27 GMT-3
Pierre,
Personally, I find the math very difficult to understand. That is why I
like the DEMOs on the page referenced. If you check them out and click
through them carefully, I think it helps to make the algorithm clear by
stepping through examples graphically.
just my 2 cents,
Bob Sinclair
CCIE #10427, CISSP, MCSE
www.netmasterclass.net
----- Original Message -----
From: "Pierre-Alex Guanel" <pierreg@planetkc.com>
To: "Bob Sinclair" <bsinclair@netmasterclass.net>; "Ccielab@Groupstudy.Com"
<ccielab@groupstudy.com>
Sent: Thursday, July 08, 2004 4:49 PM
Subject: Re: Advanced: OSPF Algorithm
> Thanks Bob,
>
> Simple to understand you said?
>
> Shortest Path Problem
> Given a connected graph G=(V,E), a weight d:E->R+ and a fixed vertex s in
V,
> find a shortest path from s to each vertex v in V.
>
>
> Dijkstra's Algorithm
> Dijkstra's algorithm is known to be a good algorithm to find a shortest
> path.
> 1.. Set i=0, S0= {u0=s}, L(u0)=0, and L(v)=infinity for v <> u0. If |V|
=
> 1 then stop, otherwise go to step 2.
> 2.. For each v in V\Si, replace L(v) by min{L(v), L(ui)+dvui}. If L(v)
is
> replaced, put a label (L(v), ui) on v.
> 3.. Find a vertex v which minimizes {L(v): v in V\Si}, say ui+1.
> 4.. Let Si+1 = Si cup {ui+1}.
> 5.. Replace i by i+1. If i=|V|-1 then stop, otherwise go to step 2.
> The time required by Dijkstra's algorithm is O(|V|2). It will be reduced
to
> O(|E|log|V|) if heap is used to keep {v in V\Si : L(v) < infinity}.
>
> http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml
>
> Pierre
>
>
> ----- Original Message -----
> From: "Bob Sinclair" <bsinclair@netmasterclass.net>
> To: "Pierre-Alex Guanel" <pierreg@planetkc.com>; "Ccielab@Groupstudy.Com"
> <ccielab@groupstudy.com>
> Sent: Wednesday, July 07, 2004 7:41 PM
> Subject: Re: Advanced: OSPF Algorithm
>
>
> > Pierre,
> >
> > A good understanding of OSPF requires a feel for the Dijkstra algorithm.
> > Check out the java-based demos at the link below. I think the demos
show
> > that the math is really very easy to understand. Amazing that this
> > algorithm from the 1950s is still useful today.
> >
> > http://tinyurl.com/xlim
> >
> > HTH,
> >
> > Bob Sinclair
> > CCIE #10427, CISSP, MCSE
> > www.netmasterclass.net
> >
> >
> > ----- Original Message -----
> > From: "Pierre-Alex Guanel" <pierreg@planetkc.com>
> > To: "Ccielab@Groupstudy.Com" <ccielab@groupstudy.com>
> > Sent: Wednesday, July 07, 2004 2:23 PM
> > Subject: Advanced: OSPF Algorithm
> >
> >
> > > How does OSPF add the cost of the links?
> > >
> > > >From what I have seen, it does not seem like the cost in the packet
> gets
> > > updated from hop to hope.
> > >
> > > The process of flooding just passes the original lsa along, unaltered.
> > >
> > > >From what I read, the OSPF algorithm knows how to find all the costs
> and
> > add
> > > them up from the LSA using the Djakstra algorithm.
> > >
> > > Yes I know its all explained in RFC 2178 ...section 16, but I am
> looking
> > at
> > > a simple explaination.
> > >
> > > thanks,
> > >
> > > Pierre
> > >
> > >
This archive was generated by hypermail 2.1.4 : Sun Aug 01 2004 - 10:11:50 GMT-3