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:
Here is the solution to that example:
Now here is the question I've been given:
Which I believe (though I am not sure) has been written incorrectly and I have changed it to:
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:
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).