You are here:

Advanced Math/Dijkstra's Algorithm

Advertisement

Expert: - 3/3/2008


Question

dijkstra's algorithm
Hi

I am currently taking part in a computer course, and have to retake a maths exam, as i failed the first time. I found out which questions i was having trouble answering, and so need help. So what is the answer to the following question, and how would it be done? (SEE IMAGE, the excerpt below was taken from a PAST exam paper)

Thank You

PS Would it be alright to ask further questions, and mark them as private?

Answer
Questioner:  jason williams
Private: no

I am currently taking part in a computer course, and have to retake a maths exam, as i failed the first time. I found out which questions i was having trouble answering, and so need help. So what is the answer to the following question, and how would it be done? (SEE IMAGE, the excerpt below was taken from a PAST exam paper)

Thank You

PS Would it be alright to ask further questions, and mark them as private?  

==========================================
Hi, Jason,

It is alright to ask questions.  It is NOT alright to mark them private.

........................................

Alas, it has been a while (like 25 years) since I saw this, but I think it goes like this:

From c, find the nearest node.
That is d, dist = 4.  P = cd
From d, find the nearest node, but not c.
That is e, dist = 1 + 4 = total 5  P = cde
From e, find the nearest node, but not c,d.
That is b, dist = 1 + 5, total = 6  P = cdeb.
From b find the nearest node, not c,d,e.
That is a, dist = 2, 2 + 6 = 8, P = cdeba.
From a, find the nearest node, not cdeb.
That is f, dist = 3, 3 + 8 = 11. P = cdebaf WE ARE THERE in 11.

Now backtrack to a to find a shorter path.
From a, find the next nearest node, not cdeb. OR f.
There are none.

Backtrack to b.
From b, find the next nearest node, not cde or a.
There are none.

Backtrack to e.
From e, find the next nearest node, not cd or b.
That is f, dist = 5, P = cdef, total = 10 and we are there in 10, A SHORTER PATH.

Continue this backtracking and searching until you have backtracked to c and found no more possible paths.

Paul Klarreich

Expertise

I can answer questions in basic to advanced algebra (theory of equations, complex numbers), precalculus (functions, graphs, exponential, logarithmic, and trigonometric functions and identities), basic probability, and finite mathematics, including mathematical induction. I can also try (but not guarantee) to answer questions on Abstract Algebra -- groups, rings, etc. and Analysis -- sequences, limits, continuity. I won't understand specialized engineering or business jargon.

Experience

I taught at a two-year college for 25 years, including all subjects from algebra to third-semester calculus.

Education/Credentials
-----------

©2012 About.com, a part of The New York Times Company. All rights reserved.