PGDDSA Study · Semester 1

PGD01C01

Module 2 · Graph Theory

Seven Bridges, Shortest Path and Travelling Salesman

Core Titles

Key headlines and terms for quick recall

Königsberg Seven Bridges problem (Euler 1736)
Shortest path problem
Dijkstra's algorithm — single-source, non-negative weights, $O((V+E)\log V)$
Bellman–Ford — handles negative weights, $O(VE)$
Floyd–Warshall — all-pairs shortest path, $O(V^3)$
Travelling Salesman Problem (TSP) — NP-hard
Heuristics: nearest-neighbour, MST-based, branch-and-bound

Basic Idea

What it is, why it matters, how it works

Königsberg seven bridges (Euler 1736)

The town of Königsberg has 4 land masses joined by 7 bridges. Question: can someone walk through the town crossing each bridge exactly once?

Euler modelled it as a multigraph (land masses = vertices, bridges = edges) and observed: all 4 vertices had odd degree. By his theorem this is impossible — there is no Eulerian trail. This problem launched graph theory.

Shortest path problem

Given a weighted graph and a source vertex, find the minimum-cost path to every other vertex.

Dijkstra's algorithm (non-negative weights):

Initialise $d[v] = \infty$ for all $v$ , $d[s] = 0$ .
Repeatedly pick the unvisited vertex $u$ with smallest $d[u]$ .
Relax each neighbour: if $d[u] + w(u,v) < d[v]$ , update $d[v]$ .
Repeat until all vertices processed. Complexity: $O((V+E)\log V)$ with a min-heap.

Bellman–Ford — also works with negative edge weights and detects negative cycles. Complexity $O(VE)$ .

Floyd–Warshall — all-pairs shortest paths via dynamic programming. Complexity $O(V^3)$ .

Travelling Salesman Problem (TSP)

A salesman must visit $n$ cities and return to the start with minimum total distance, visiting each city once.

TSP is NP-hard. No known polynomial algorithm.
Exact methods: branch-and-bound, dynamic programming ( $O(n^2 2^n)$ — Held–Karp).
Heuristics: nearest neighbour, 2-opt, MST-based ( $\le 2 \cdot \text{OPT}$ ), Christofides ( $\le 1.5 \cdot \text{OPT}$ for metric TSP).

Why this matters in Data Science

GPS routing, network protocols (OSPF uses Dijkstra), logistics, last-mile delivery, manufacturing tour planning.

Mind Map

Visual structure of the concept

SHORTEST-PATH & TSP
├── Seven Bridges (Euler 1736)
│   └── No Eulerian trail (4 odd-degree vertices)
├── Single-Source Shortest Path
│   ├── Dijkstra   — non-neg weights, O((V+E)log V)
│   └── Bellman-Ford — handles negatives, O(VE)
├── All-Pairs
│   └── Floyd-Warshall  O(V³)
└── TSP (NP-hard)
    ├── Exact: Held-Karp O(n² 2ⁿ)
    └── Heuristics
        ├── Nearest neighbour
        ├── 2-opt
        └── Christofides ≤ 1.5·OPT

Exam Q&A

Part A (2 marks) and Part B (20 marks) style questions

Part A (2 marks each)

Q1. What is the Königsberg seven bridges problem? Whether one can walk through Königsberg crossing each of the 7 bridges exactly once. Euler showed it impossible.

Q2. What is the complexity of Dijkstra's algorithm with a heap? $O((V+E)\log V)$ .

Q3. Why does Dijkstra fail on negative edges? Because once a vertex's distance is "finalised," a later negative edge could improve it, violating Dijkstra's greedy assumption.

Q4. Is TSP polynomial-time solvable? No — TSP is NP-hard.

Part B (20 marks)

Q. Explain Dijkstra's algorithm with an example. Discuss the Travelling Salesman Problem and its heuristic approaches.

Dijkstra's algorithm (pseudo-code).

for each v in V:  d[v] = ∞; prev[v] = NIL
d[s] = 0
Q = priority queue of all v keyed by d[v]
while Q not empty:
    u = extract-min(Q)
    for each neighbour v of u:
        alt = d[u] + w(u, v)
        if alt < d[v]:
            d[v] = alt; prev[v] = u; decrease-key(Q, v, alt)

Example. Source $A$ , graph: $A{-}B$ =4, $A{-}C$ =1, $C{-}B$ =2, $B{-}D$ =1, $C{-}D$ =5.

Step	Visited	d[B]	d[C]	d[D]
init	–	∞	∞	∞
pick A	A	4	1	∞
pick C	A,C	3	1	6
pick B	A,B,C	3	1	4
pick D	all	3	1	4

Shortest path $A \to D$ : $A \to C \to B \to D$ , cost 4.

Travelling Salesman Problem (TSP). Given $n$ cities with pairwise distances, find the minimum-cost tour visiting every city exactly once and returning to start. TSP is NP-hard — runtime grows exponentially in the worst case.

Heuristic approaches.

Nearest neighbour — start at any city, repeatedly go to the closest unvisited city. Simple but can produce tours up to $\log n \cdot \text{OPT}$ .
2-opt / 3-opt — local search: repeatedly swap pairs of edges to remove crossings.
MST-based — construct an MST, double the edges, find Eulerian circuit, shortcut repeated visits. Gives a $\le 2 \cdot \text{OPT}$ tour for metric TSP.
Christofides' algorithm — refines MST approach with minimum-weight perfect matching on odd-degree vertices. Achieves $\le 1.5 \cdot \text{OPT}$ for metric TSP.
Metaheuristics — simulated annealing, genetic algorithms, ant colony — for very large instances.

Real-world: vehicle routing, chip wiring, DNA sequencing.

Paths, Circuits, Eulerian and Hamiltonian Circuits Planar Graphs