1
$\begingroup$

So I've found out a few things and was wondering if someone could verify if I'm doing this correctly. So here is an example I've been given: enter image description here

Here is the solution to that example:

enter image description here

Now here is the question I've been given: enter image description here

Which I believe (though I am not sure) has been written incorrectly and I have changed it to: enter image description here

Finally I got this for my final solution, and I just need a verification that I am doing this correctly. Information on Dijkstra's algorithm with directed vertices is sort of vague and I haven't found any real good information via google, any help is greatly appreciated. Thanks in advance, here is my final solution: enter image description here

$\endgroup$
1
$\begingroup$

The first column was omitted because it will always be zero. Remember that we are trying to compute the shortest distance from $v_1$ to all other vertices. So we should have something like: \begin{array}{c|cccccc} S & v_1 & v_2 & v_3 & v_4 & v_5 & v_6 \\ \hline \{\} & \color{red}{\boxed{0}} & \infty & \infty & \infty & \infty & \infty \\ \{v_1\} & \boxed{0} & 7& \infty & \color{red}{\boxed{2}} & \infty & \infty \\ \{v_1, v_4\} & \boxed{0} & \color{red}{\boxed{6}}& \infty & \boxed{2} & \infty & \infty \\ \{v_1, v_4, v_2\} & \boxed{0} & \boxed{6}& 10 & \boxed{2} & \color{red}{\boxed{7}} & \infty \\ \{v_1, v_4, v_2, v_5\} & \boxed{0} & \boxed{6}& \color{red}{\boxed{9}} & \boxed{2} & \boxed{7} & \infty \\ \{v_1, v_4, v_2, v_5, v_3\} & \boxed{0} & \boxed{6}& \boxed{9} & \boxed{2} & \boxed{7} & \color{red}{\boxed{12}} \\ \{v_1, v_4, v_2, v_5, v_3, v_6\} & \boxed{0} & \boxed{6}& \boxed{9} & \boxed{2} & \boxed{7} & \boxed{12} \\ \end{array}

So for example, a path of shortest length from $v_1$ to $v_3$ is given by $v_1 \to v_4 \to v_2 \to v_5 \to v_3$, which has a total distance of $2 + 4 + 1 + 2 = 9$. Remember that once we put a box around a tentative shortest distance, that number will never change in any subsequent rows (it is our final shortest distance, and is no longer tentative).

$\endgroup$
  • 1
    $\begingroup$ Thanks so much Adriano. I finally understand what I'm doing now. $\endgroup$ – Yusha Apr 22 '15 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.