In the given weighted graph, the weights represent distance between the corresponding vertices. The shortest distance between vertex A and vertex E is \( d \). The number of paths with distance \( d \) is \( p \). The value of \( d/p \) is ______.
Show Hint
List every possible route from A to E along the given edges, add up the weights, and find the minimum total distance and how many routes achieve it.
Step 1: Labelling Nodes by Shortest Distance from A:
Start at A with a distance label of $0$, then work outward, relaxing each edge to find the shortest known distance to every node.
Direct neighbours of A: $B$ gets label $2$ (via $A\text{-}B$), $C$ gets label $1$ (via $A\text{-}C$).
Step 2: Relaxing the Remaining Edges:
From $C$, going to $B$ gives $1 + 1 = 2$, which ties the existing label on $B$, so $B$ now has TWO equally short ways to reach it: directly from $A$, and via $C$.
From $B$ (label $2$), going to $E$ gives $2 + 4 = 6$, so $E$ gets a tentative label of $6$.
From $C$, going to $F$ gives $1 + 2 = 3$, so $F$ gets label $3$; then from $F$ to $E$ gives $3 + 3 = 6$, matching the label already on $E$.
From $B$, going to $D$ gives $2 + 5 = 7$, then from $D$ to $E$ gives $7 + 3 = 10$, which is worse than $6$, so this route is dropped.
Step 3: Counting Paths at the Shortest Label:
The final shortest label on $E$ is $d = 6$.
Since $B$ itself can be reached in two equally short ways (direct, and via $C$), both extend through edge $B\text{-}E$ into two distinct shortest paths to $E$: $A\text{-}B\text{-}E$ and $A\text{-}C\text{-}B\text{-}E$.
The route through $F$ gives a third distinct shortest path: $A\text{-}C\text{-}F\text{-}E$.
So the count of shortest paths is $p = 3$.
Final Answer:
Dividing the shortest label by the number of shortest paths reaching it gives the required ratio.
\[ \boxed{d/p = 6/3 = 2} \]
