🔍 Graph Search Algorithms — DFS & A* Search

Implementation and comparison of two graph search algorithms — Depth First Search (DFS) and A* Search — on a weighted directed graph. The goal is to find a path from node A to node G and compare total path distances.

---

📋 Table of Contents

• Project Overview
• Graph Structure
• Algorithm 1 — Depth First Search (DFS)
• Algorithm 2 — A* Search
• Comparison
• Libraries Used
• How to Run
• Project Structure

---

📌 Project Overview

This project implements two classic AI search algorithms on the same weighted graph and compares their paths and total distances:

Algorithm	Approach	Uses Heuristic?
DFS	Explores as deep as possible before backtracking	❌ No
A*	Uses cost + heuristic to find optimal path	✅ Yes

---

📐 Graph Structure

Weighted Directed Graph (A → G):

graph = {
    'A': [('B', 6), ('C', 2)],
    'B': [('D', 5), ('E', 3)],
    'C': [('F', 4)],
    'D': [('G', 2)],
    'E': [('G', 6)],
    'F': [('G', 1)],
    'G': []
}

Visual Structure:

        A
       / \
    (6)B  C(2)
      / \   \
   (5)D (3)E (4)F
      \    \   \
      (2)G (6)G (1)G

Heuristic Values (h) for A*:

Node	Heuristic (h)
A	7
B	6
C	4
D	3
E	5
F	2
G	0

---

🔵 Algorithm 1 — Depth First Search (DFS)

How it works:

• Starts at node A
• Explores each branch as deep as possible before backtracking
• Uses visited set to avoid revisiting nodes
• Returns the first path found to goal G

Key Functions:

def dfs(graph, start, goal, path=None, visited=None)
def calculate_distance(graph, path)

Result:

Metric	Value
Path Found	A → B → D → G
Total Distance	13

Distance Breakdown:

A → B = 6
B → D = 5
D → G = 2
Total = 13

⚠️ DFS does NOT guarantee the shortest path — it returns the first path found.

---

🟡 Algorithm 2 — A* Search

How it works:

• Uses a priority queue (min-heap) via heapq
• Each node is evaluated by: f(n) = g(n) + h(n)
  • g(n) = actual cost from start to current node
  • h(n) = heuristic estimate from current node to goal
• Always expands the node with the lowest f score
• Guarantees the optimal (shortest) path

Heuristic Used: Pre-defined admissible heuristic h

Key Formula:

f(n) = g(n) + h(n)

Expected Path:

A → C → F → G
Total Distance = 2 + 4 + 1 = 7

✅ A* finds the optimal path with minimum total cost.

---

📊 Comparison

Metric	DFS	A*
Path	A → B → D → G	A → C → F → G
Total Distance	13	7
Optimal?	❌ No	✅ Yes
Uses Heuristic?	❌ No	✅ Yes
Strategy	Depth-first	Best-first (f = g + h)

🏆 A* wins — finds the shorter path (cost 7) vs DFS (cost 13).

---

🛠️ Libraries Used

heapq   (priority queue for A*)

No external libraries needed — pure Python implementation.

---

🚀 How to Run

1. Clone the repository:

git clone https://github.com/hamza93-ai/Graph-Search-Algorithms-DFS-Astar.git

2. Open the notebook:

jupyter notebook graph_search_dfs_astar.ipynb

3. Run all cells to see DFS and A* results and comparison.

---

📁 Project Structure

Graph-Search-Algorithms-DFS-Astar/
│
├── graph_search_dfs_astar.ipynb   # Main notebook
└── README.md                      # Project documentation

---

👤 Author

Hamza Asif