From: Pierre-Alex Guanel (pierreg@planetkc.com)
Date: Thu Jul 08 2004 - 17:49:28 GMT-3
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
> >
> > _______________________________________________________________________
> > Please help support GroupStudy by purchasing your study materials from:
> > http://shop.groupstudy.com
> >
> > Subscription information may be found at:
> > http://www.groupstudy.com/list/CCIELab.html
This archive was generated by hypermail 2.1.4 : Sun Aug 01 2004 - 10:11:50 GMT-3