Question

In a given weighted graph shown below, what is the value of the expression \( (p + d)^2 \), where: 
[i.] Alphabets A, B, C, D, E, and F denote the nodes 
[ii.] Numbers 1 to 6 denote the weights between two nodes 
[iii.] \( d \) = shortest distance between node A and node E 
[iv.] \( p \) = number of paths with distance \( d \) 

• A. 100
• B. 64
• C. 81
• D. 121

Hint:

In weighted graphs, identify the shortest path using path enumeration or Dijkstra’s algorithm. To compute expressions involving path count, list all distinct paths with the same minimal distance.

Answer 1

The Correct Option is C

We are given a weighted undirected graph and asked to evaluate the expression \( (p + d)^2 \), where:

- \( d \) = shortest distance from node A to node E
- \( p \) = number of paths from A to E with that distance

Let us evaluate all possible paths from A to E:

1. \( A \rightarrow B \rightarrow E \): \( 3 + 3 = 6 \)
2. \( A \rightarrow D \rightarrow E \): \( 1 + 5 = 6 \)
3. \( A \rightarrow D \rightarrow F \rightarrow E \): \( 1 + 2 + 3 = 6 \)

Other paths like \( A \rightarrow B \rightarrow D \rightarrow E \) or those involving node C are longer than 6.

Hence, the shortest distance is:
\[ d = 6 \] and the number of such shortest paths is: \[ p = 3 \]
Therefore, the value of the expression is: \[ (p + d)^2 = (3 + 6)^2 = 9^2 = \boxed{81} \]