In the graph, we have to find the shortest distance between Newark and Cape May. I have tried using the Dijkstra algorithm but I can't seem to figure out how it would work. According to my working, the distance is coming out to be 175 whereas it should be 85.
Shortest distance between two vertices
algorithmsdiscrete mathematicsgraph theory
Related Solutions
As Justin Benfield answered, letting $(X,Y)$ to be the coordinates of the unknown point, the distance to point $(x_i,y_i)$ is given by $$d_i^2=(X-x_i)^2+(Y-y_i)^2$$ and we want to minimize $$F=\sum_{i=1}^7 d_i$$ that is to say to find $X$ and $Y$ such that $$\frac{dF}{dX}=0 \qquad, \qquad \frac{dF}{dY}=0$$ Writing all of that means that you want $$\frac{dF}{dX}=\sum_{i=1}^7 \frac{X-x_i}{\sqrt{(X-x_i)^2+(Y-y_i)^2}}=0$$ $$\frac{dF}{dY}=\sum_{i=1}^7 \frac{Y-y_i}{\sqrt{(X-x_i)^2+(Y-y_i)^2}}=0$$ which is quite complicated (in particular because of the interdependency of the unknown variables as already mentioned by Justin Benfield).
The problem becomes very simple if instead, you consider minimizing the sum of the squares of the distances that it is to say $$G=\sum_{i=1}^7 d_i^2$$ In such a case, we have$$\frac{dG}{dX}=2\sum_{i=1}^7 (X-x_i)=0 \qquad , \qquad \frac{dG}{dY }=2\sum_{i=1}^7 (Y-y_i)=0$$ which show that $X$ and $Y$ are just the means of the $x_i$'s and $y_i$'s.
Using your data points $$\left( \begin{array}{ccc} \text{city} & x & y \\ A & 73 & 96 \\ B & 105 & 81 \\ C & 139 & 101 \\ D & 165 & 65 \\ E & 147 & 19 \\ F & 115 & 49 \\ G & 100 & 13 \end{array} \right)$$ this would just lead to $X=\frac{844} 7\approx 120.6$ and $Y=\frac{424} 7\approx 60.6$. For such coordinates, we should have $F\approx 288$.
We can consider that this first step gives an approximate solution and we can start iterating the minimization of $F$ (this is quite tedious but perfectly doable). And guess what ? The solution is $X\approx 118.2$ and $Y\approx 56.3$ for which $F\approx 287$. Not far, isn't it ?
You could also take into account the fact you are going once a year to each of the cities except $A$ where you are going twice. The same procedure will put your place at $X\approx 112.5$ and $Y\approx 67.5$. As you see, we can play a lot with this kind of problems.
But you could also say that what you want is to minimize the maximum distance to drive. Still more complicated but still doable, the result being $X\approx 111.9$ and $Y\approx 59.3$. Still close !
Don't worry ! You will learn this kind of things sooner or later and I am sure that you will enjoy them.
I would approach this directly as follows:
Pick two vertices $u, v \in G$ such that $d_{G}(u, v) \geq 2$. Then we have the two following cases:
$\textbf{Case 1}$: $G = P_{n}$, then $u=x_{j} - x_{j+1} - \cdots - x_{k}=v$ where $1 \leq j \leq k \leq n$. We can pick any vertex on the path $u-v$ and label it as $x_{l}=z$ where $j < l < k$, and we achieve $d_{G}(u, v) = d_{G}(u, z) + d_{G}(z, v)$.
$\textbf{Case 2}$: Let G be some arbitrary graph. Let a path $P:u-v$ such that $d_{G}(u, v) \geq 2$. Now assume there exists another path $Q:u-v$ that is internally disjoint to the path $P$, then the path $Q$ must have the same length as path $P$. Since if it was shorter, then we would contradict the definition of $d_{G}(u, v)$. From this we again attain $d_{G}(u, v) = d_{G}(u, z) + d_{G}(z, v)$.
Best Answer
Djikstra's algorithm gives Newark-Woodbridge-Camden-Cape May with a distance of $165$.
I suspect that your error was to permanently box Atlantic City (on $130$) before you had boxed Camden (on $80$).