[10%] You are analyzing the routing latencies for a constellation of 4 satellites (Nodes A, B, C, D). Below is the adjacency list with the latency between specific nodes:

Adjacency List:

• A → B: 10
• A → C: -5
• C → B: 4
• B → D: 5
• D → C: 2
• D → A: 3

Requirement: You need to analyze the latency characteristics of the network so that shortest communication paths can be efficiently determined when needed.

Questions:

(1) [4%] Based on the specific properties of the edges in this graph and the problem requirement, identify the single most appropriate standard algorithm to use. Explain your choice by pointing out the specific graph feature that disqualifies other algorithms, and explicitly state why at least one other commonly used shortest-path algorithm would fail or be inappropriate in this case.

(2) [2%] Let $M$ be the initial $4 \times 4$ distance matrix used at the start of your chosen algorithm. Please construct and write down $M$ clearly. (Note: Use “$\infty$” for non-existing edges and “0” for self-loops. Order: A, B, C, D)

(3) [4%] After the algorithm completes execution:

    (a) [2%] What is the final shortest path cost from Node D to Node B? Please trace the path logic (e.g., D → … → B).

    (b) [2%] State the asymptotic Time Complexity $\Theta$ of this algorithm.