Integer Multiplication, Graph Basics, and Dijkstra's Algorithm

Integer Multiplication, Graph Basics, and Dijkstra's Algorithm

10.1 Integer Multiplication

10.1.1 Motivation: Why Learn Integer Multiplication?

Under the divide-and-conquer design strategy we have so far covered merge sort and quick sort. Merge sort splits an array in half, sorts each half, and merges the sorted halves. Quick sort splits by a pivot, sorts the two sides, and joins them. Both follow the same pattern: divide the problem, solve the smaller pieces, combine. The third algorithm in this family is integer multiplication, and the natural first reaction is: we all already know how to multiply two integers, so what is the big deal? Why does multiplication deserve its own divide-and-conquer treatment?

The answer has two layers. The first layer: a computer must perform multiplication, so the operation itself matters. Every processor carries out millions of multiplications per second, and the way it does so determines how fast programs run. The second and sharper layer: when we talk about integer multiplication here, we mean multiplication of very large integers — numbers so big they cannot be processed in one go in the ALU (arithmetic-logic unit) of a computer. The ALU is the part of the processor that performs arithmetic on machine words, and a single machine word holds a fixed number of bits — typically 32 or 64. A number with hundreds or thousands of bits does not fit into a single machine register, so the elementary-school algorithm we all know — multiply digit by digit and add up the partial products — takes time quadratic in the number of bits: $O(n^2)$ time for two $n$-bit integers. The whole reason for studying multiplication under divide and conquer is to do better than that quadratic wall for such large operands.

Real-world: large-integer arithmetic is not a classroom toy. RSA and other public-key encryption algorithms live on multiplication of very large numbers — an RSA key is an integer of hundreds or thousands of bits — which is exactly why the efficiency of this operation matters in practice. The method we develop works in binary, where splitting an $n$-bit number into halves is natural and the shift factors become powers of two.

The approach is justified by its time complexity, not by novelty. Multiplication can be done in many ways; we pick this one because it carries an explanation that justifies its runtime. Watch for that pattern throughout this section: every rewrite we perform exists so that the final time-complexity argument becomes clean and provable.

10.1.2 The Elementary Split of an n-Bit Integer

We take an $n$-bit integer $i$ and divide it into two halves: the high half $i_h$ (the most significant $n/2$ bits) and the low half $i_l$ (the least significant $n/2$ bits). Do the same for a second $n$-bit integer $j$, giving $j_h$ and $j_l$. The value of each original number is then:

$$i=i_h\cdot 2^{n/2}+i_l,j=j_h\cdot 2^{n/2}+j_l$$

Here $i_h,i_l,j_h,j_l$ are each $n/2$-bit integers. Read the equation as a place-value statement: $i_h\cdot 2^{n/2}$ places the high half into the top $n/2$ bit positions, and adding $i_l$ fills the bottom $n/2$ positions. In decimal this is exactly how we write a four-digit number like $1980=19\times 10^2+80$: the high half 19 sits two digits above the low half 80. This is a recursive process: each $n/2$-bit half is itself split into two $n/4$-bit halves, and so on, until we reach single-bit (or single-digit) numbers where multiplication is trivial.

Multiplying the two expansions out gives the transformed product. Let us do the algebra line by line instead of jumping to the answer. Substitute both halves:

$$\begin{array}{rlr}i\times j& =(i_h\cdot 2^{n/2}+i_l)(j_h\cdot 2^{n/2}+j_l)& \\ & =i_h\cdot 2^{n/2}\cdot j_h\cdot 2^{n/2}+i_h\cdot 2^{n/2}\cdot j_l+i_l\cdot j_h\cdot 2^{n/2}+i_l\cdot j_l& \text{(distribute: four terms)}\\ & =i_h\cdot j_h\cdot 2^n+i_h\cdot j_l\cdot 2^{n/2}+i_l\cdot j_h\cdot 2^{n/2}+i_l\cdot j_l& \text{(combine 2n/2⋅2n/2=2n)}\\ & =i_h\cdot j_h\cdot 2^n+(i_h\cdot j_l+i_l\cdot j_h)\cdot 2^{n/2}+i_l\cdot j_l& \text{(group the two middle terms)}\end{array}$$

The final line is the transformed product:

$$i\times j=i_h\cdot j_h\cdot 2^n+(i_h\cdot j_l+i_l\cdot j_h)\cdot 2^{n/2}+i_l\cdot j_l$$

What did this transformation accomplish? We broke the multiplication of two $n$-bit numbers into four multiplications of $n/2$-bit numbers — $i_h\cdot j_h$, $i_h\cdot j_l$, $i_l\cdot j_h$, $i_l\cdot j_l$ — plus three additions. The additions do not worry us: adding two $n$-bit numbers takes at most $O(n)$ time, and we are not paying anything extra for them. Multiplication, on the other hand, cannot be done in $O(n)$ time — it is what takes $O(n^2)$ in the school method. That asymmetry — cheap additions versus expensive multiplications — is the entire reason this restructuring is worth attempting.

To make the split concrete in binary, take $i=13$ and $j=11$. In binary these are 4-bit numbers: $i=1101_2$ and $j=1011_2$, so $n=4$ and $n/2=2$. The split gives $i_h=11_2=3$, $i_l=01_2=1$, $j_h=10_2=2$, $j_l=11_2=3$, and indeed $13=3\times 2^2+1$ and $11=2\times 2^2+3$. The four sub-multiplications are $3\times 2=6$, $3\times 3=9$, $1\times 2=2$, and $1\times 3=3$, and the equation reconstructs $13\times 11=6\times 2^2+(9+2)\times 2^1+3=24+22+3=143$. A quick sense-check: $13\times 11=143$. This is the same process the decimal worked example later in this section runs through in detail.

10.1.3 Naive Divide and Conquer: Four Multiplications

The split of the previous section gives the recurrence for the running time $T(n)$ of multiplying two $n$-bit numbers, where the basic operation is multiplication (we count multiplications, not additions):

$$T(n)=4T(n/2)+\Theta (n)$$

Here $4T(n/2)$ is the time for the four multiplications of $n/2$-bit numbers, and the $\Theta (n)$ term is the time taken by all the other processing — in this case the three additions, which cost at most $O(n)$. The lecture states it in one sentence: the problem of multiplying two $n$-bit numbers is divided into multiplication of four $n/2$-bit numbers plus some extra processing, and the extra processing is some addition which is equal to $\Theta (n)$; addition can be done at the max at $n$ time. A good habit to practice: explain any recurrence you write in plain English, so that writing it down becomes automatic. If you can say "four subproblems of half the size plus linear extra work" in one breath, you can also write $4T(n/2)+\Theta (n)$ without hesitating.

Applying the master theorem: here $a=4$ (four subproblems), $b=2$ (each subproblem is half the size), and $f(n)=\Theta (n)$. The master theorem compares $f(n)$ with the critical function $n^{{\log }_{b}a}=n^{{\log }_{2}4}=n^2$. Since $f(n)=\Theta (n)$ is polynomially smaller than $n^2$ (case 1 of the master theorem: $f(n)=O(n^{2-\epsilon })$ for $\epsilon =1$), the recurrence is dominated by the recursive part:

$$T(n)=4T(n/2)+\Theta (n)=\Theta (n^2)$$

That is an anticlimax: the plain schoolbook algorithm was already running in $\Theta (n^2)$, and after all this dividing and combining we are back at $\Theta (n^2)$ — no advantage in time complexity. The only thing we gained is the ability to break a size-$n$ problem into size-$n/2$ problems at all. Not much of an improvement; but notice that we are not going to change the process at all. The last equation stays exactly as it is. We are only going to rewrite that same equation in a different way, and that rewrite alone will buy us the improvement.

The same lesson appears in an unexpected place — building a heap. The time to build a heap is $O(n)$, not $O(n\log n)$. When we first analyzed the process with a casual, trivial analysis we got $n\log n$; on a careful, structured, professional analysis we realized it was always $n$. The process did not change between the two analyses — our analysis was the problem. Exactly the same thing is about to happen here: no change in the process, only in the way we look at the equation.

10.1.4 Rewriting the Equation: p1, p2, p3

We keep the exact same process and the exact same last equation. We introduce three variables. Define:

$$p_1=(i_h+i_l)(j_h+j_l),p_2=i_h\cdot j_h,p_3=i_l\cdot j_l$$

Consider $p_1$ in this form itself — the sum of the halves times the sum of the halves. Expanding it, the products $i_h{j}_h$, $i_h{j}_l$, $i_l{j}_h$, and $i_l{j}_l$ are all covered, which is why $p_1$ was defined that way: one product term $(i_h+i_l)(j_h+j_l)$ contains all four ingredients we need. Now subtract $p_2$ and $p_3$ from $p_1$:

$$\begin{array}{rlr}{p}_1-p_2-p_3& =(i_h+i_l)(j_h+j_l)-i_h{j}_h-i_l{j}_l& \\ & =i_h{j}_h+i_h{j}_l+i_l{j}_h+i_l{j}_l-i_h{j}_h-i_l{j}_l& \text{(expand p1)}\\ & =i_h{j}_l+i_l{j}_h& \text{(cancel ihjh and iljl)}\end{array}$$

The two high-by-low cross terms survive and everything else cancels — this is exactly the middle term of the expanded product. So we can write the full product using only $p_1,p_2,p_3$:

$$i\times j=p_2\cdot 2^n+(p_1-p_2-p_3)\cdot 2^{n/2}+p_3$$

Check that this matches the original expansion term by term: $p_2=i_h{j}_h$ sits at the $2^n$ position (the high place), $p_1-p_2-p_3=i_h{j}_l+i_l{j}_h$ sits at the $2^{n/2}$ position (the middle), and $p_3=i_l{j}_l$ sits at the $2^0$ position (the low place). Nothing changed mathematically — the product is the same number — but the way we compute it is about to become cheaper.

Now count what each piece costs, and count carefully. $p_1=(i_h+i_l)(j_h+j_l)$ is two $n/2$-bit additions plus one $n/2$-bit multiplication — consider $p_1$ in its non-expanded form, otherwise you will think there are many multiplications inside it. $p_2$ is one $n/2$-bit multiplication, and $p_3$ is one $n/2$-bit multiplication. The whole equation then contains three $n/2$-bit multiplications, two subtractions, and two additions. The multiplications by $2^n$ and $2^{n/2}$ are just left shifts — constant-time operations that account for at most $\Theta (n)$ time in total, so we do not even need to count them separately.

The improved recurrence is:

$$T(n)=3T(n/2)+\Theta (n)$$

with the $\Theta (n)$ now covering all the additions and subtractions of the multiplication process. By the master theorem with $a=3$, $b=2$, $f(n)=\Theta (n)$, the critical exponent is $n^{{\log }_{2}3}$:

$$T(n)=3T(n/2)+\Theta (n)=\Theta (n^{{\log }_{2}3})=\Theta (n^{1.585})$$

The lecture states the value as "$n$ power log 3 to the base 2", which solves to about $n^{1.5}$ or $n^{1.58}$; precisely, ${\log }_{2}3\approx 1.585$, so the running time is $\Theta (n^{1.585})$. From $O(n^2)$ down to $O(n^{1.585})$ may look like a modest gain in a trivial analysis, but for integers of very large size it is a solid improvement — although it seems slower initially because of the extra pre-computations (dividing the $n$-bit number into halves, doing the additions and subtractions), for very large integers this multiplication saves a considerable amount of time. For smaller integers the overhead of the splitting, additions, and subtractions can outweigh the benefit, so the normal multiplication algorithm is the right choice there; this divide-and-conquer version is for large integers. The method is known as the Karatsuba algorithm, published by Karatsuba and Ofman in 1962, and it is the standard example of beating a naive method by restructuring the arithmetic rather than the process.

Comparison: the three multiplication schemes side by side.

When to pick which: the school method wins for small integers, where the overhead of splitting and recombining is not worth it; the three-product divide-and-conquer wins for large integers, where the improved exponent pays off. The naive four-product scheme is a stepping stone, not a competitor — its only value is showing that the process itself can be decomposed, which sets up the rewrite.

Visual intuition — why one fewer multiplication changes the exponent. Draw the recursion trees for the two recurrences. For $4T(n/2)$, each node of size $n$ spawns 4 children of size $n/2$, so at depth $k$ there are $4^k$ subproblems each of size $n/2^k$. The tree has ${\log }_{2}n$ levels; at the bottom there are $4^{{\log }_{2}n}=n^2$ leaves of size 1 — the quadratic wall. For $3T(n/2)$, each node spawns 3 children instead of 4; the depth is still ${\log }_{2}n$, but the bottom level has only $3^{{\log }_{2}n}=n^{{\log }_{2}3}\approx n^{1.585}$ leaves. Plot the two growth curves $n^2$ and $n^{1.585}$ for $n$ from 1 to $10^6$: they look close at small $n$ and visibly diverge at large $n$ — at $n=2^{32}$, $n^2=2^{64}$ but $n^{1.585}=2^{50.7}$, about 8000 times smaller. That gap is exactly what the "for very large integers" caveat means.

10.1.5 The Integer Multiplication Algorithm

There are exactly three multiplications of $n/2$-bit numbers in the algorithm — one in each of $p_1,p_2,p_3$ — and the rest is additions and subtractions, which is why the recurrence is $3T(n/2)+O(n)$ and why the recurrence must be clear: three multiplications of $n/2$-bit numbers, two subtractions, and two additions.

Note that the slide's listing names the products differently from the derivation above: here $p_1$ is the low product $x_l\cdot y_l$ and $p_2$ is the high product $x_r\cdot y_r$, while in the derivation $p_1$ was the sum-product $(i_h+i_l)(j_h+j_l)$ and $p_3$ was the low product $i_l\cdot j_l$. Only the names are swapped — the algebra is identical. In the listing's naming, $p_3-p_1-p_2=(x_l+x_r)(y_l+y_r)-x_l{y}_l-x_r{y}_r=x_l{y}_r+x_r{y}_l$ is exactly the cross term, placed at the $2^{n/2}$ position between the low product $p_1$ and the high product $p_2\cdot 2^n$. Whichever naming you use, the equation is the same product, so pick one naming per solution and stay consistent with it.

Decimal works identically to binary, with the base swapped: in the decimal worked example the factor $2^{n/2}$ becomes $10^{n/2}$ because the base is 10. You should convert the decimal numbers of the example into binary and redo the process — with binary the shifts become powers of two, and the shift-by-two-positions effect becomes literal bit shifting.

10.1.6 Worked Example: 1980 × 2315 in Decimal

The lecture works only the first iteration or two in class because a full recursion is tedious, and deliberately uses decimal so the writing goes faster — the process is exactly the same as binary, not easier. The multiplication is $1980\times 2315$, both four-digit numbers, so $n=4$ and $2^{n/2}=10^2$ in base 10. The full walkthrough below follows the derivation's naming: $p_1$ is the sum-product, $p_2$ the high product, $p_3$ the low product.

The lecture stops the in-class walkthrough after the first iterations because the process is long but mechanical; the important part is being clear on the first iteration. Notice how the recursion unwound: we went down to single digits on one branch ($p_1$), combined it, then used the result inside the next combine — and the same unwind happens independently inside $19\times 23$ and $80\times 15$. If you convert the same numbers to binary and rerun the process, the $10^k$ factors become $2^k$, and each multiply-by-a-power-of-two becomes a plain shift.

10.1.7 Beyond This Algorithm: FFT-Based Multiplication

For anyone interested, there is an even faster approach: using a more complex divide-and-conquer algorithm called the fast Fourier transform (FFT), two $n$-bit integers $i$ and $j$ can be multiplied in $O(n\log n)$ time. The idea is to treat the bit strings as polynomials, multiply the polynomials with the FFT in $O(n\log n)$ time, and read off the integer product from the coefficients — the same divide-and-conquer family, applied to the coefficients instead of the bits. This is only for information and optional reading for those curious — FFT itself is a topic studied in later coursework, but the fact that multiplication can be driven down to $O(n\log n)$ shows the same design strategy pushing further. (For exactness: the best-known FFT-family algorithms for integer multiplication run in $O(n\log n\log \log n)$ time; $O(n\log n)$ is the clean picture the theory points toward.)

Real-world: FFT-based multiplication is what arbitrary-precision arithmetic libraries actually use for gigantic operands — libraries such as GMP that back big-integer arithmetic in programming languages switch to FFT-based methods once the operands grow past tens of thousands of digits. The same divide-and-conquer idea we built here underlies the big-integer arithmetic inside RSA-style encryption systems, where the operands are the hundreds- or thousands-of-bits integers that cannot be processed at one go in the ALU — the motivation we started with.

10.2 Graph Basics

10.2.1 What Is a Graph?

A graph is an ordered pair $(V,E)$, where $V$ is a set of nodes called vertices and $E$ is a collection of pairs of vertices called edges. The order matters in the pair itself: $(V,E)$ names the vertex set first and the edge collection second. The word "collection" rather than "set" is deliberate — a collection may hold two identical pairs, which is how we allow parallel edges later. For implementation purposes, vertices and edges are positions and stored elements: a position is an abstract data type (ADT) that can store elements, so when you implement a graph in code, each vertex and each edge can be a position that stores data — a vertex can store its name, a number, or anything else, and an edge can store the weight of that edge.

The running example is an airport network: each vertex represents an airport and stores its three-letter airport code, an edge represents a flight route, and the numbers written on the edges are the mileage of the routes. So a graph has vertices, edges, and edges can carry values or weights.

Real-world: graph modeling appears everywhere — electronic circuits (printed circuit boards), transportation networks (for example the road route between two cities), highway networks, flight networks, computer networks (a LAN is a network; the internet is the biggest example), and databases (an ER diagram: an employee entity type and a department entity type are vertices, and the relationship "employee works for a department" is the edge connecting them). In every case the modeling decision is the same: identify the objects (vertices) and the relationships between objects (edges).

10.2.2 Directed, Undirected, and Mixed Edges

A directed edge is an ordered pair $(u,v)$ of vertices. The first vertex $u$ is the origin and the second vertex $v$ is the destination, shown with an arrow from $u$ to $v$. Example: a flight operating between two airports only in one direction — say a flight from one city to another that does not come back the other way — is a directed edge; it goes from the origin to the destination only.

An undirected edge is an unordered pair of vertices. Example: a route existing between two airports — the route can be traveled both ways, like a bridge connecting two places, where you can go from place A to place B and back.

A mixed graph has both kinds of edges in one graph. The important skill is deciding, from the nature of the question, whether you are modeling a directed graph or an undirected graph — you must logically visualize the statement. The moment you see the words "flight route", do not conclude "directed" automatically: if only a route exists between the places, you can model it as undirected; it is the actually operating flight that must be a directed edge. In a directed graph all the edges are directed; in an undirected graph all the edges are undirected.

Choosing the edge type: the three options side by side.

When to pick which: read the scenario and ask whether the relationship can be traversed in reverse — one direction means directed, both directions means undirected, and a mixture in one scenario means mixed.

The same situational judgment applies to electrical wiring and water pipes: model them as directed or undirected depending on whether the current, or the water, is allowed to flow in both directions or only one direction. For water, in principle it can flow either way through a pipe, so an undirected edge is natural unless the system is built for one-way flow.

Visual intuition. Picture the airport example as a chart: vertices drawn as labeled circles (three-letter codes like SFO, LAX, PVD), edges drawn either as plain line segments (route exists both ways) or as arrows (operating flight from origin to destination). The shape of the drawing does not matter — what matters is which pairs are connected and whether the connections are arrows or plain segments.

10.2.3 Graph Terminology: Endpoints, Incidence, Adjacency, Degree

The terminology builds layer by layer, each term defined from the earlier ones. For an edge with endpoints $u$ and $v$: $u$ and $v$ are the end vertices (or endpoints) of that edge. In the sample graph, $u$ and $v$ are endpoints of the edge labeled $a$.

Edges incident on a vertex: the edges that touch that vertex. In the sample undirected graph, the edges $a$, $d$, and $b$ are incident on vertex $v$. The edges incident on vertex $z$ are $h$, $i$, and $j$ — the two parallel edges shared with $x$ and the self-loop at $z$ (both defined below).

Adjacent vertices: two vertices joined by an edge. $u$ and $v$ are adjacent (edge $a$); another pair is $w$ and $x$ (joined by edge $e$).

Degree of a vertex: the number of edges incident on that vertex. In the sample graph, vertex $x$ has degree 5 — the edges $b,e,g,i,h$ are all incident on it. The degree of vertex $w$ is left as a quick exercise — count the edges touching $w$: $c,e,f,d$ — four edges, so $\mathrm{deg}(w)=4$.

Visual intuition. Draw the graph as a loose hexagon: $u$ at the top, $v$ and $w$ below it, $x$ and $y$ at the bottom, $z$ off to the side. Connect $u$ to $v$ (edge $a$) and to $w$ (edge $c$); connect $v$ to $w$ (edge $d$) and to $x$ (edge $b$); connect $w$ to $x$ (edge $e$) and to $y$ (edge $f$); connect $x$ to $y$ (edge $g$) and to $z$ twice (edges $h$ and $i$ running side by side); and draw a loop from $z$ back to itself (edge $j$). The two parallel edges $h$ and $i$ appear as two separate curves between the same two circles; the self-loop $j$ appears as a small circle attached to $z$ alone.

10.2.4 Parallel Edges and Self-Loops

Parallel edges are edges having the same endpoints — in the sample graph, the edges $h$ and $i$ are parallel edges, both joining the same two vertices $x$ and $z$. Parallel edges appear in real graphs naturally: two flights on the same route at different times of day are parallel edges in the airport graph, one per flight, between the same two airports.

A self-loop is an edge whose endpoints are the same — in the sample graph, the edge $j$ is a self-loop; its two endpoints are the same vertex $z$. A self-loop in a city map is a street that curves around and returns to its own starting intersection.

A graph with no self-loops and no parallel edges is called a simple graph. Most of the graphs we analyze in this course are simple, but the definitions must handle the exceptions: when a graph is not simple, the degree counting rule still works — the self-loop just lands both of its counts on one vertex.

10.2.5 Paths and Cycles

A path is a sequence of alternating vertices and edges. It begins with a vertex and ends with a vertex, and each edge in the sequence is preceded and followed by its endpoints.

A simple path is a path in which all its vertices and edges are distinct — no vertex and no edge is repeated. Example from the sample graph: the path $v,b,x,h,z$ (following the blue-colored edges) is a simple path. The longer walk $u,c,w,e,x,g,y,f,w,d,v$ is a path but not a simple path, because the vertex $w$ is repeated.

A cycle is a circular sequence of alternating vertices and edges — a path that comes back to its starting point. A simple cycle is a cycle in which all vertices and edges are distinct other than the starting vertex; the cycle concept itself accounts for the starting vertex being repeated, since a circular sequence must return to where it began. The blue-colored cycle in the sample graph is a simple cycle; the brown-colored one is not a simple cycle because a vertex is repeated inside it. So the rule of thumb: in a path no vertex can be repeated; in a cycle, only the starting vertex may be repeated.

Visual intuition. Trace the blue path $v,b,x,h,z$ on the sample graph: a pencil that never leaves the circles and never revisits one. Now trace the brown walk $u,c,w,e,x,g,y,f,w,d,v$: the pencil revisits $w$, so the walk is not simple. For cycles, imagine a circular tour of the graph — it must close on itself, so the starting circle is revisited by definition, and that single repeat is the only one allowed for simplicity.

10.2.6 Modeling Real Scenarios as Graphs

Three worked modeling decisions show how to choose directed, undirected, or mixed:

Co-authorship (undirected). Build a graph whose vertices are researchers of a discipline and whose edges connect pairs of researchers who have co-authored a paper or book. This is undirected because collaboration is a symmetric relation: if author A has co-authored something with B, then B has definitely co-authored that same thing with A. There is no direction to the edge because the relationship cannot hold in one direction only.

Inheritance (directed). In object-oriented programming, the inheritance relation between classes is directed — the edges are directed because inheritance only goes in one direction; it is an asymmetric relation. If class $B$ inherits from class $A$, the arrow points from $B$ to $A$ (or from the parent to the child, depending on convention), but the reverse relationship does not hold: $A$ does not inherit from $B$.

City map (mixed). A city map is modeled by a graph whose vertices are intersections and dead ends and whose edges are stretches of streets without intersections. This is a mixed graph: there can be one-way streets, which give directed edges, and streets allowing traffic in both directions, which give undirected edges. A mixed graph is rare, but here the situation demands it — and it is your job, based on the situation, to take that call.

The same situational judgment applies to electrical wiring and water pipes: model them as directed or undirected depending on whether the current, or the water, is allowed to flow in both directions or only one direction. When in doubt, ask "can this relationship be traversed in reverse?" — yes means undirected, no means directed, both in one graph means mixed.

10.2.7 Three Key Properties

These properties matter later for algorithm analysis, so they are worth being thorough about.

Property 1 — sum of degrees. For any undirected graph $G$ with $m$ edges:

$$\sum _{v\in V}\mathrm{deg}(v)=2m$$

The sum of the degrees of all the vertices equals twice the number of edges. Reason: each edge is counted twice — once for each of its endpoints — so the total is $2m$, and this holds for every undirected graph.

Property 2 — simple graph edge bound. A simple graph is a graph with no self-loops and no multiple edges — between two vertices there cannot be more than one edge. If $G$ is a simple graph with $n$ vertices and $m$ edges:

$$m\le n(n-1)$$

The number of edges is at most on the order of $n^2$. Take a simple graph and work it out to confirm the bound: with $n=4$ vertices, the maximum is $4\times 3=12$ edges. The exact maximum depends on the edge type: for a simple undirected graph, the tight bound is $m\le n(n-1)/2$ (each of the $n(n-1)$ ordered vertex pairs collapses to one unordered pair), while $m\le n(n-1)$ is the exact maximum for a simple directed graph, where the ordered pairs $(u,v)$ and $(v,u)$ count as two distinct edges. The lecture's statement $m\le n(n-1)$ is the directed bound and, for either type, a valid upper bound of order $n^2$ — which is what the algorithms later in the course actually use.

Property 3 — in-degree and out-degree. For a directed graph with $m$ edges, define in-degree of a vertex as the number of edges incoming to it, and out-degree as the number of edges outgoing from it. Then:

$$\sum _{v\in V}\text{in-degree}(v)=m,\sum _{v\in V}\text{out-degree}(v)=m$$

For directed graphs we do not talk about "degree" (all incident edges) because incident includes both incoming and outgoing; instead we use in-degree or out-degree, and each of those sums equals the number of edges $m$ — not $2m$. This makes logical sense without computation: every edge contributes exactly one incoming count at its destination and one outgoing count at its origin. A practice graph was given for homework: compute in-degrees and out-degrees for every vertex and verify both sums — five minutes of practice is enough, and it is assigned, not optional.

Visual intuition. Imagine counting handshakes at a party: every handshake (edge) involves two hands (endpoint counts), so the total number of hands involved is twice the number of handshakes — that is Property 1. For a directed graph, imagine one-way deliveries: each delivery is received once (in-degree count) and sent once (out-degree count), so the total received equals the total sent equals the number of deliveries.

10.2.8 Weighted Graphs and More Applications

A weighted graph is a graph in which each edge has an associated numerical value called the weight of the edge — it can represent distance, cost, and so on. In the airport example, the weight of an edge represents the distance in miles between the endpoint airports. Weighted graphs are the models used when the relationships have a cost or quantity attached: a road graph with travel times, a network graph with cable costs, a flight graph with mileage.

Real-world: weighted-graph modeling shows up in movie preference systems — viewers are one set of vertices and movies are another set of vertices; there is an edge from a user to a movie if the user viewed that movie, and the edges are weighted by the rating the viewer gave. This is a bipartite structure: edges only ever join a viewer vertex to a movie vertex, never two viewers. Nobody restricts you to drawing a graph in a perfect grid — a graph can be drawn any way that is convenient to read, as long as vertices and edges are clear. More examples worth reading through on your own build the intuition for modeling scenarios as graphs.

10.3 Dijkstra's Algorithm

10.3.1 The Single-Source Shortest Path Problem

The first algorithm under graphs is the single-source shortest path algorithm — Dijkstra's algorithm. Given a graph and a starting vertex $S$, the algorithm computes the shortest distance from $S$ to every other vertex: the output is the shortest distance from $S$ to $A$, from $S$ to $B$, from $S$ to $C$, and so on — the distances of all the vertices from a given start vertex $S$. "Single source" is the key phrase: one start vertex, many destinations. The output is not one path but a complete answer set — the shortest distance to every vertex, plus enough bookkeeping to recover the paths themselves.

Two assumptions are required. The graph must be connected — if the graph were two disconnected pieces, you could not compute a distance from $S$ to vertices in the other piece, since no path exists. And the edge weights must be non-negative — the reason for this is examined in detail after the algorithm is understood; other algorithms allow negative weights, but Dijkstra needs non-negative edges.

Real-world: this problem is the mathematical core of GPS navigation. A navigation app is given the road graph with travel-time weights and computes the shortest route from your current position — the single source — to the destinations you care about, using exactly the machinery developed here.

10.3.2 Relaxation of an Edge

The heart of Dijkstra's algorithm is a procedure called relaxation of an edge. We relax an edge $(u,v)$ with weight $w(u,v)$. Each vertex carries two pieces of information: $d[v]$, the cost of reaching $v$ from the source — the best distance found so far — and $\pi [v]$, the predecessor of $v$ on that best route. (For the moment, take the current cost values as already computed; the procedure that sets them comes next.)

The relaxation check for a directed edge from $u$ to $v$ is:

$$\text{if }d[v]>d[u]+w(u,v),\text{ then }d[v]=d[u]+w(u,v)\text{ and }\pi [v]=u$$

In words: if the already-calculated cost of reaching $v$ from the source is greater than the cost of reaching $v$ through $u$ — that is, the cost of reaching $u$ plus the weight of the edge $u\to v$ — then the route through $u$ is cheaper, so update the cost of $v$ to $d[u]+w(u,v)$ and record the predecessor of $v$ as $u$. If the check fails, nothing happens: the current route to $v$ is already at least as good as the route through $u$, so both $d[v]$ and $\pi [v]$ stay unchanged.

Worked numbers, first case (update). Suppose the cost of reaching $u$ from the source is 8, the cost of reaching $v$ from the source is 11, and the edge $u\to v$ has weight 2. The check: is $11>8+2$? Yes. So we update $d[v]=8+2=10$, because we found a route to $v$ that is cheaper than the previously known one, and we set $\pi [v]=u$ — the predecessor of $v$ is $u$, meaning you should come to $v$ through $u$.

Worked numbers, second case (update). The cost of reaching $u$ is 5, the edge $u\to v$ has weight 2, and the cost of reaching $v$ through some other path is 9. Since $9>5+2=7$, the better route exists, so $d[v]$ is updated to 7 and the predecessor becomes $u$.

Worked numbers, third case (no update). The cost of reaching $u$ is 5 and the edge weight is 2, so the route through $u$ costs 7 — but an alternate route reaches $v$ at a cost of 6, which is less than 7, so we do nothing: the relaxation step leaves both $d[v]$ and $\pi [v]$ unchanged.

This relaxation step is the most important step of Dijkstra's algorithm — if you do not understand it, you will not understand the algorithm at all. Everything else in the algorithm exists to decide which edges to relax in which order; the relaxation itself is the only place where distances and paths are ever improved.

Why "relaxation"? The intuitive picture: the edge had a very high cost attached; we relax it to have a cheaper cost, which is closer to our goal of shortest paths.

Real-world: the commute analogy — if you know two places and two routes between them, whichever route is cheaper to reach the place becomes your updated shortest path. That everyday decision is exactly the relaxation step. You hear a new route to a shop costs less than the route you knew; your mental "distance to the shop" drops and the route you remember changes to the new one.

10.3.3 Initialize Single Source

The second building block is the procedure initialize single source. For every vertex in the graph, we start by assuming that no vertex is reachable from the source. Concretely:

• $d[S]=0$ — the cost of reaching the source from the source itself is zero.
• For every other vertex $v$, $d[v]=\infty$ — conceptually none of the vertices are reachable from the source.
• For every vertex, $\pi [v]=\text{nil}$ — if a vertex is not reachable, there is no question of a predecessor.

That is the starting point of the algorithm. The infinity is not a number to be reached — it is a flag meaning "no route known yet". Because every real route has finite cost, the first relaxation that finds any route to $v$ will satisfy $\infty >d[u]+w(u,v)$ and install the first real value. This is why the strict-greater-than comparison works with infinity: any finite number beats it.

10.3.4 The Algorithm

With relaxation and initialization understood, the algorithm is short:

1. Initialize single source: set $d[S]=0$, $d[v]=\infty$ and $\pi [v]=\text{nil}$ for all other vertices.
2. Let $S$ (the visited list) be empty, and put all the vertices of the graph into $Q$. $Q$ is just an array of vertices — no special data structure is needed at this point.
3. While $Q$ is not empty:

• Extract the minimum from $Q$: pick the vertex $u$ with the smallest current distance $d[u]$. This vertex is now processed — add it to the visited list.
• For every vertex $v$ adjacent to $u$ (for every edge connected to $u$), relax the edge $(u,v)$: apply the check of Section 10.3.2, updating $d[v]$ and $\pi [v]$ if a cheaper route through $u$ exists.

That is the whole algorithm — it writes exactly the steps we would perform by hand. The two subtleties to keep hold of: the extracted vertex is the minimum-distance vertex among those still unvisited, and relaxation may change costs and predecessors of other unvisited vertices. Note the second point carefully: extracting a vertex fixes its own distance forever, but it also improves the distances of its neighbors — which is why later extractions can and do find already-improved values.

Visual intuition — the growing cloud. Imagine the visited vertices as a shaded cloud that starts with just $S$ and swallows one vertex per iteration, always the unvisited vertex with the smallest current distance. Each new vertex drags its unvisited neighbors closer to the cloud by relaxing its outgoing edges. The algorithm ends when the cloud covers everything. This cloud picture is exactly the one used in Section 10.3.8 to explain why negative weights break the algorithm.

10.3.5 Worked Example on a Five-Vertex Graph

Run Dijkstra's algorithm on the directed graph with vertices $A,B,C,D,E$ and the following directed edges and weights: $A\to B$ weight 10, $A\to C$ weight 3, $C\to B$ weight 4, $C\to D$ weight 8, $C\to E$ weight 2, $E\to D$ weight 9, $B\to D$ weight 2, $B\to C$ weight 1, $D\to E$ weight 7. The source is $A$. Relate the vertices to places you know and the weights to kilometers — that is all the graph is.

This backtracking is the aim of the algorithm — nobody will update these after the algorithm ends, so you must explicitly write out or highlight the shortest paths in the diagram. Note the order in which vertices were processed: $A,C,E,B,D$ — always the minimum-distance vertex among those remaining. The minimum was read from the current, up-to-date values: after Step 2 the unvisited candidates were $B:7,D:11,E:5$, so $E$ came next even though $B$'s value was known earlier.

Visual intuition. Draw the five vertices $A$ at the left, $C$ just below it, $B$ to the right of $C$, $D$ to the right of $B$, and $E$ between $C$ and $D$. Label every edge with its weight and every arrowhead. After the run, the shortest-path tree (the edges used by the final routes: $A\to C$, $C\to B$, $B\to D$, $C\to E$) forms a tree rooted at $A$ — each vertex except the source has exactly one incoming tree edge, its predecessor. Highlighting these four edges is the "explicitly write out the shortest paths" step.

10.3.6 Time Complexity: Array Implementation

Analyze Dijkstra's algorithm step by step, assuming $Q$ is implemented as an ordinary array or linked list.

Initialize single source: we must set $d[v]=\infty$ for every vertex one by one, which forces us to visit all vertices at least once — so this step takes $\Theta (|V|)$ time, where $|V|$ is the number of vertices.

The while loop: it runs until $Q$ is empty, and $Q$ holds all $|V|$ vertices, so the loop body executes $|V|$ times.

Find and remove the minimum: finding the minimum element of an array takes $\Theta (|V|)$ time (no sorting needed — just scan). Doing this once per loop iteration gives $|V|\times |V|=|V{|}^2$ time for the two statements together.

Relaxation over edges: the for loop relaxes each edge of the graph at most once. How many edges can a vertex be connected to? At most the total number of edges — the degree of a vertex is bounded by the number of edges $m$. Using the earlier property: in a directed graph the sum of in-degrees of all the vertices is $m$, so the total relaxation work is $O(|E|)$ — not $|V|\times |E|$, because the $e$ already accounts for the sum of in-degrees of all vertices. This is where the degree property pays off.

Total for the array implementation:

$$O(|V{|}^2+|E|)=O(|V{|}^2)$$

Since $|V{|}^2$ dominates $|E|$, the time complexity of Dijkstra's algorithm with an array is $O(|V{|}^2)$.

Instantiate the analysis on the five-vertex worked-example graph: $|V|=5$ vertices and $|E|=9$ edges. Initialization costs about 5 steps, the loop runs 5 times, each extract-min scans up to 5 entries ($5\times 5=25$ scan steps total), and the relaxation loop examines each of the 9 edges once. The total is on the order of $25+9=34$ steps — dominated by the $5^2=25$ from the scans, exactly as the formula $O(|V{|}^2+|E|)$ predicts. For a dense graph with $|E|$ near $|V{|}^2$, the $|V{|}^2$ term swallows everything.

Visual intuition. Finding the minimum of an array is like scanning a shelf of price tags for the cheapest item: you look at every tag once and remember the best so far — no rearranging needed. That is $n$ steps per scan, and Dijkstra performs such a scan once per extracted vertex.

10.3.7 Time Complexity: Heap Implementation

We know a better data structure for extracting the minimum: the heap, also known as a priority queue. Re-run the analysis with $Q$ implemented as a heap.

Initialize single source: still $\Theta (|V|)$ — and the build-heap time of $O(|V|)$ is accounted for right here inside initialization; while building the heap we can set all the initial distances at the same time.

The while loop: still $|V|$ iterations.

Find and remove the minimum: extracting the minimum from a heap takes $O(\log |V|)$ time. That is where the difference appears: instead of $|V|$ per extraction we pay $\log |V|$, so the loop plus extraction costs $|V|\log |V|$ instead of $|V{|}^2$.

Relaxation as decrease-key: each relaxation of an edge is nothing but decreasing the key of a vertex in the heap — during the worked example the costs only went down (10 to 7, infinity to 3), never up. The heap has procedures called increase-key and decrease-key, and changing the value of a node in a heap requires a heapify that takes $O(\log |V|)$ time. So for each edge the relaxation costs $O(\log |V|)$, and over all $|E|$ edges it costs $|E|\log |V|$.

Together:

$$O(|V|\log |V|+|E|\log |V|)=O((|V|+|E|)\log |V|)=O(|E|\log |V|)$$

The last step uses the degree property again: in a connected graph the sum of degrees of all vertices is $2m$, and in a directed graph the sum of in-degrees (or out-degrees) is $m$, so the total degree is upper-bounded by the number of edges $e$ — which is definitely the upper bound — so $|V|+|E|$ can be replaced by $|E|$ alone. So the heap-based implementation runs in $O(|E|\log |V|)$.

Comparison: array versus heap implementation.

When to pick which: for dense graphs, where $|E|$ is close to $|V{|}^2$, the array implementation's $O(|V{|}^2)$ is fine and simpler; for sparse graphs, where $|E|$ is close to $|V|$, the heap implementation's $O(|E|\log |V|)$ is far faster. The heap wins whenever the graph has few edges per vertex.

10.3.8 Why Edge Weights Must Be Non-Negative

The basic principle on which Dijkstra's algorithm works: if all the weights are non-negative, adding an edge can never make a path shorter. Every time the algorithm finds the node with the lowest cost and relaxes its outgoing edges, it adds the edge weight onto the already-accumulated cost — an addition process. If every added amount is non-negative, the cost of reaching a place can only grow as we go further, so the cost of a place we have already reached will never be reduced later. That guarantee is exactly why picking the shortest candidate at each step always ends up being correct.

What if some weights are negative? Consider the small graph: source $A$, edges $A\to D$ weight 4, $D\to C$ weight 1, $D\to F$ weight 5, and $F\to C$ weight $-8$. From $A$, $d[D]=0+4=4$. Processing $D$'s incident edges: $d[C]=4+1=5$ and $d[F]=4+5=9$. Now the visited vertices form a "cloud" — the shaded area of already-processed vertices, whose outgoing edges have all been relaxed. Next the minimum is $C$ at 5, so $C$ is processed and its processing is over; only later is $F$ reached at 9, and relaxing $F\to C$ gives $9+(-8)=1$ — C's cost drops from 5 to 1 after C has already been finalized. The frozen vertex $C$ can no longer be reprocessed, so the algorithm silently keeps the wrong answer. Even one or two negative edges break Dijkstra's algorithm: as per the greedy method, the processing of $C$ was done, and we cannot redo it.

If all the edge costs are the same, the algorithm still works and remains optimal.

10.3.9 Greedy Strategy

Under which design strategy does Dijkstra's algorithm fall? We have studied two design strategies so far — the greedy method and divide and conquer. Dijkstra's algorithm is a greedy method. The reason: our ultimate aim is the shortest path from the source to all other vertices, and we keep picking the minimum — extract-min, the minimum-cost vertex — under the assumption that picking the shortest path or shortest edge will always end up getting the shortest global path. We do not even consider the destination initially; we are only worried about the current vertex's incident edges, and out of those we pick the shortest edge, assuming we will end up with the shortest path for the whole graph. Local optimality is leading to global optimality — that is the defining feature of the greedy method.

The greediness also explains the failure mode: a greedy algorithm is only as good as its local-choice rule, and when a negative edge makes a frozen vertex's value drop later, the "never revisit" rule becomes a bug rather than a feature. The same greedy pattern returns in the next session with the second greedy graph algorithm — minimum spanning tree — which also commits to cheapest edges, never revisits them, and needs the same careful justification of why the local choice is safe.

10.3.10 Applications of Dijkstra's Algorithm

Real-world: Dijkstra's algorithm is everywhere in practice. OSPF (Open Shortest Path First), the routing protocol used in IP networks, is built on it. GPS and geographical maps use it, and so does the A* algorithm — a well-known path-finding algorithm and an advanced version of Dijkstra itself; Google Maps does not directly use Dijkstra but uses A*, a version of Dijkstra whose basic concepts remain the same. All routing algorithms and all path-finding algorithms for computing the distance between two places can use this approach. There is also an interactive visualization tool worth playing with to see how Dijkstra behaves on a practical example — watch the visited "cloud" grow as the algorithm runs.

Exam Guidance Summary

• Quiz 2: scheduled for the window from 5th November to 10th November, 30 minutes, 20 questions. It will contain questions from graph topics — so the basics of graphs and Dijkstra's algorithm are directly quiz material.
• Integer multiplication: the recurrence construction and master-theorem evaluation are exam-worthy; practice writing the recurrence in plain English and practice the binary version of the worked example. The exam-worthy core is the two recurrences — $T(n)=4T(n/2)+\Theta (n)$ and the improved $T(n)=3T(n/2)+\Theta (n)$ — and the master-theorem evaluation of each.
• Graph basics: expect scenario questions that ask you to decide directed vs undirected vs mixed, plus the three properties — sum of degrees equals $2m$, the simple-graph edge bound, and in-degree/out-degree sums. The practice graph for in/out degrees was assigned; work it out.
• Dijkstra's algorithm: expect analysis questions comparing the array implementation $O(|V{|}^2)$ with the heap implementation $O(|E|\log |V|)$, the relaxation mechanism, and the reason non-negative weights are required. The two greedy graph algorithms — shortest path and minimum spanning tree — are both really important not only from the exam perspective but from an application perspective as well.
• Minimum spanning tree: read about MST before the next session — it will be covered very quickly, since it is the second greedy graph algorithm.
• Self-study video material is mandatory: the class runs in flipped mode — sessions cover topics that are not explained in detail in the self-study videos, and questions will come from those self-study topics as well. There is no list of "important" videos; all of them matter equally, like a contact session. Bellman-Ford (negative-weight shortest paths) is one such topic — it appears in the self-study material and must not be ignored.
• Textbook problems are exam material: exam questions are taken from the textbook without warning — for example, the "criminal robot" style question on the mid-sem exam was a textbook exercise problem. The stock-span problem will be there, and the clue for it was already given in class. Textbook problem solutions are not provided — you have to work them out.
• Marks distribution: there is no hard percentage rule between pre-mid-sem and post-mid-sem topics, but the intention is to include more from post-mid-sem topics.
• Comprehensive exam: open book. Feedback about question comprehensibility has been noted and will be addressed in the comprehensive exam.
• Assignment: submission requires a design document justifying your choices; wherever the assignment says binary tree, you may use a binary search tree instead if it gives better efficiency — justify that selection in the design document. Assignment date extension is not possible.
• Course reality check: this is a five-credit course with many topics; it will be difficult, especially for those without a computer-science background. The last session is 12th November, possibly with one extra session if needed.

Key Industry Applications

• Integer multiplication / RSA: the divide-and-conquer multiplication (and its FFT variant) powers the large-integer arithmetic at the heart of RSA encryption algorithms; in binary the split is natural and shifts become powers of two.
• FFT-based multiplication: fast Fourier transform gives $O(n\log n)$ multiplication of two $n$-bit integers — used in arbitrary-precision arithmetic for very large operands.
• OSPF routing: Open Shortest Path First, a core internet routing protocol, is an application of Dijkstra's algorithm.
• GPS and map navigation: Dijkstra-style shortest path computation underlies GPS and geographical maps.
• A* algorithm / Google Maps: A* is an advanced version of Dijkstra; Google Maps uses A*, whose basic concepts remain the same as Dijkstra's.
• Path-finding in general: all routing algorithms and path-finding algorithms for distance between two places use this approach.
• Graph modeling: electronic circuits (printed circuit boards), transportation and highway networks, flight networks, computer networks (LAN, the internet), and ER diagrams in databases are all graphs — entities are vertices, relationships are edges.
• Movie preference systems: viewers and movies as two vertex sets, with rating-weighted edges — a weighted-graph model of recommendations.
• Research collaboration networks: co-authorship graphs connect researchers who have published together — undirected because collaboration is symmetric.
• The commute analogy: choosing the cheaper of two known routes to a place is relaxation in everyday life.