Lecture notes
Further Maths, notes on algorithms for OCR MEI
- Module
- Unit 13 - Statistics 1
- Institution
- OCR
Notes with explanations for modeling with algorithms for OCR MEI
[Show more]
Seller
Follow
Content preview
Dijsktra's AlgorithmFInding the shortest path
It is guarenteed to find us the best possible path, however it is relatively slow as it checks everything.
This is Dijkstra's Algorithm to find the shortest path from S to T through a network.
1. Label the start vertex, S, with the final label, 0.
2. Record a working value att every vertec, Y, that is ditectly connected to the vertex, x, that hs just recieved its
final label
1. Working value at Y = final value at X + weight of arc XY
2. If there is already a working value at Y, it is only replaced if the new value is smaller.
3. Once a vertex has a inal label it is not revisited and its working values are no longer considered
4. Look at the working values at all vertices without final labels. Select the smallest working value. This now
becomes the final label at the vertex. (If two vetticees have the smallest working value either may be given i
final label first).
5. Repeat steps 2 and 3 until the desitnation vertex , T, recieves its final label.
,6. To find the shortest path, trace back from T to S. Given that B already lies on the route, include arc AB
whenever final label of B - final label of A = weight of arc AB.
,Algorithms - Bin Packing
The bin pakcing uses sorting of numbers and is a massive simplification of a real problem.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller 2poppc68. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for £9.49. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
75323 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy revision notes and other study material for 14 years now