2. **Visit Neighboring Nodes:** For the current node, consi…

how are tentative distances calculated

Tentative distances are a key concept in algorithms like Dijkstra's algorithm, which is used to find the shortest path from a starting node to all other nodes in a weighted graph. The term "tentative distance" refers to the current known shortest distance from the starting node to a particular node, which may be updated as the algorithm proceeds.

Here's how tentative distances are calculated:

---

### **Step-by-Step Explanation:**

1. **Initialization:**

- **Starting Node:**
- Set the tentative distance to the starting node as **0** because the distance from the starting node to itself is zero.
- **All Other Nodes:**
- Set the tentative distances to all other nodes as **infinity** (∞) to represent that they are initially unreachable.

2. **Visit Neighboring Nodes:**

When the algorithm selects the current node (starting with the starting node), it examines all of its unvisited neighbors.

3. **Calculating Tentative Distances:**

For each unvisited neighbor of the current node:

- **Retrieve Current Tentative Distance:**
- Get the tentative distance to the **current node** (let's denote this as **D_current**).
- **Edge Weight:**
- Determine the **weight of the edge** from the current node to the neighbor node (denote this as **W_edge**).
- **Calculate New Tentative Distance:**
- **New Tentative Distance = D_current + W_edge**
- This represents the distance from the starting node to the neighbor node **via the current node**.
- **Compare and Update:**
- If the **new tentative distance** is **less than** the neighbor node's previously recorded tentative distance, update it with the new, smaller value.

---

### **Example:**

Let's illustrate this with a simple example.

#### **Graph Structure:**

- **Nodes:** A, B, C
- **Edges and Weights:**
- A → B (weight = 4)
- A → C (weight = 2)
- B → C (weight = 5)

#### **Algorithm Steps:**

1. **Initialization:**

- Tentative distances:
- **A:** 0 (starting node)
- **B:** ∞
- **C:** ∞

2. **First Iteration (Current Node: A):**

- **Neighbors of A:** B and C

**Calculating Tentative Distances to Neighbors:**

- **Neighbor B:**

- **D_current (A):** 0
- **W_edge (A → B):** 4
- **New Tentative Distance to B:** 0 + 4 = 4
- **Previous Tentative Distance to B:** ∞
- **Update:** Since 4 < ∞, update tentative distance to B as 4.

- **Neighbor C:**

- **D_current (A):** 0
- **W_edge (A → C):** 2
- **New Tentative Distance to C:** 0 + 2 = 2
- **Previous Tentative Distance to C:** ∞
- **Update:** Since 2 < ∞, update tentative distance to C as 2.

- **Updated Tentative Distances:**

- **A:** 0 (visited)
- **B:** 4
- **C:** 2

3. **Second Iteration (Current Node: C):**

- Choose the unvisited node with the smallest tentative distance, which is **C** (tentative distance = 2).

- **Neighbors of C:** B

**Calculating Tentative Distances to Neighbors:**

- **Neighbor B:**

- **D_current (C):** 2
- **W_edge (C → B):** 5
- **New Tentative Distance to B:** 2 + 5 = 7
- **Previous Tentative Distance to B:** 4
- **Update:** Since 7 > 4, do not update tentative distance to B.

- **Updated Tentative Distances:**

- **A:** 0 (visited)
- **B:** 4
- **C:** 2 (visited)

4. **Third Iteration (Current Node: B):**

- **B** is the next unvisited node with the smallest tentative distance.

- No unvisited neighbors to update.

- **All nodes have been visited.**

---

### **Key Points:**

- **Tentative Distance Calculation:**

\[
\text{Tentative Distance to Neighbor} = \text{Tentative Distance to Current Node} + \text{Weight of Edge to Neighbor}
\]

- **Purpose:**

- This calculation helps determine if there's a shorter path to the neighbor node through the current node.

- **Updating Tentative Distances:**

- If the new calculated tentative distance is **smaller** than the previously recorded tentative distance for that neighbor, **update** it.
- This ensures that the algorithm always has the shortest known distance from the starting node to each node at every step.

- **Why It Works:**