Anki Deck Changes

Note 1: ETH::A&D

Deck: ETH::A&D
Note Type: Algorithms
GUID: u%cN;v|jjQ

modified

Before

Front

Back

Runtime of

BFS

Runtime: {{c1::$ \mathcal{O}(|E| + |V|) $}}

Approach:

Uses:

?

The runtime of BFS:

each loop we take $O(1 + \deg(u))$ time (go through the vertex $u$'s edges
We loop a total of $|V|$ times (we visit each edge max. 1 time)

After

Front

Back

Runtime of

BFS

Runtime: {{c1::$ \mathcal{O}(|E| + |V|) $}}

Approach:

Uses:

?

Field-by-field Comparison

Field	Before	After
Extra Info	The runtime of BFS:<br><ol><li>each loop we take $O(1 + \deg(u))$ time (go through the vertex $u$'s edges</li><li>We loop a total of $\|V\|$ times (we visit each edge max. 1 time)</li></ol>

Tags: ETH::1._Semester::A&D::09._Graph_Search::2._Breadth_First_Search

Note 2: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: e=wgvK*bB^

added

New Note

Front

The shortest walk is always a path.

Back

The shortest walk is always a path.

This is due to the triangle inequality, given that no negative cycles exist.

Field-by-field Comparison

Field	Before	After
Text		The shortest walk is always {{c1::a path}}.
Extra		This is due to the triangle inequality, given that no negative cycles exist.

Tags: ETH::1._Semester::A&D::09._Graph_Search::2._Breadth_First_Search

Note 3: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Classic
GUID: rL+,fn.ulX

added

New Note

Front

The shortest path tree output by BFS is:

Back

The shortest path tree output by BFS is:

A tree from the start-vertex with levels, for each distance:

Field-by-field Comparison

Field	Before	After
Front		The shortest path tree output by BFS is:
Back		A tree from the start-vertex with levels, for each distance:<br><br><img src="paste-4c913ffd2f874833dce2fab6c179871903517c76.jpg">

Tags: ETH::1._Semester::A&D::09._Graph_Search::2._Breadth_First_Search

Note 4: ETH::A&D

Deck: ETH::A&D
Note Type: Algorithms
GUID: y@l`JCIJ<4

added

New Note

Front

Runtime of BFS (Breadth First Search)?

Back

Runtime of BFS (Breadth First Search)?

$O(|V|+|E|)$ (Adjacency List)
The runtime of BFS:

each loop we take $O(1 + \deg(u))$ time (go through the vertex $u$'s edges
We loop a total of $|V|$ times (we visit each edge max. 1 time)

Field-by-field Comparison

Field	Before	After
Name		BFS (Breadth First Search)
Runtime		$O(\|V\|+\|E\|)$ (Adjacency List)
Requirements		Directed Graph ((negative) cycles accepted, as "shortest" (not cheapest) path not affected)
Approach		<b>BFS</b> looks for the shortest paths (not cheapest) in a graph.<br><ol><li><b>Initialisation:</b> <ul> <li>Set the distance to all vertices to $\infty$ in the <code>d[v]</code> array. Set the <code>d[s] = 0</code>.</li> <li>Initialise a Queue $Q$ with $s$</li> <li>Set the dictionary <code>parent = {}</code></li> </ul> </li> <li><b>Exploration:</b><ul> <li>Dequeue the first element in the queue $v$</li> <li>For all <em>adjacent nodes</em> $u$ with distance $= \infty$ (not visited yet):<ul> <li>Set the distance <code>d[u] = d[v] + 1</code></li> <li>add $u$ to the queue</li> <li>Set the <code>parent[u] = v</code>.</li> </ul> </li> </ul> </li> <li><b>Return:</b> We return the distances and the <i>shortest path tree</i></li></ol>
Pseudocode		<img src="paste-4fbaff6bb07ad8ff63a53ac2e179914e1c8cac2b.jpg">
Use Case		Shortest Path in a directed graph
Extra Info		The runtime of BFS:<br><ol><li>each loop we take $O(1 + \deg(u))$ time (go through the vertex $u$'s edges</li><li>We loop a total of $\|V\|$ times (we visit each edge max. 1 time)</li></ol>

Tags: ETH::1._Semester::A&D::09._Graph_Search::2._Breadth_First_Search

Note 5: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Classic
GUID: L#@+crYi2-

added

New Note

Front

Bipartite Test with BFS:

Back

Bipartite Test with BFS:

We substitute bipartite for two-colourable.

While traversing the tree, in each layer, we colour all vertices with the same. If we then encounter a vertex with the same colour during traversal, it's not two-colourable.

Field-by-field Comparison

Field	Before	After
Front		Bipartite Test with BFS:
Back		We substitute bipartite for two-colourable. <br><br>While traversing the tree, <b>in each layer</b>, we <b>colour all vertices with the same</b>. If we then <b>encounter </b>a vertex with the<b> same colour</b> during traversal, it's <b>not two-colourable</b>.<br><br><img src="paste-c8749f8e54bcf6eb4c7cd1ac37ca03ea43e15fd6.jpg">

Tags: ETH::1._Semester::A&D::09._Graph_Search::2._Breadth_First_Search

Note 6: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Classic
GUID: PF|EmWOMd:

added

New Note

Front

Cost of a walk in a weighted graph $G = (V, E, c)$:

Back

Cost of a walk in a weighted graph $G = (V, E, c)$:

sum of the weight of it's edges: $\sum_{i = 0}^{l - 1} c(v_i, v_i+1)$

Field-by-field Comparison

Field	Before	After
Front		Cost of a walk in a weighted graph $G = (V, E, c)$:
Back		sum of the weight of it's edges: $\sum_{i = 0}^{l - 1} c(v_i, v_i+1)$

Tags: ETH::1._Semester::A&D::10._Shortest_Paths

Note 7: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Classic
GUID: vE[;wMoI5.

added

New Note

Front

Optimal substructure of cheapest paths:

Back

Optimal substructure of cheapest paths:

A cheapest path in a weighted graph (without negative cycles) has the optimal substructure property: any subpath is itself the cheapest path between it's endpoints.

Field-by-field Comparison

Field	Before	After
Front		Optimal substructure of cheapest paths:
Back		A cheapest path in a weighted graph (without negative cycles) has the optimal substructure property: <i>any subpath is itself the cheapest path between it's endpoints</i>.

Tags: ETH::1._Semester::A&D::10._Shortest_Paths

Note 8: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: yX`f0NZg((

added

New Note

Front

The triangle inequality in a weighted graph is $d(u, v) \leq d(u, w) + d(w, v)$

Back

The triangle inequality in a weighted graph is $d(u, v) \leq d(u, w) + d(w, v)$

This holds as if the path through $w$ was actually cheaper, then $d(u, v)$ would be wrong.

Does not hold in graphs with negative cycles.

Field-by-field Comparison

Field	Before	After
Text		The {{c1::<b>triangle inequality</b>}} in a weighted graph is {{c2::$d(u, v) \leq d(u, w) + d(w, v)$}}
Extra		This holds as if the path through $w$ was actually cheaper, then $d(u, v)$ would be wrong.<br><br>Does not hold in graphs with negative cycles.

Tags: ETH::1._Semester::A&D::10._Shortest_Paths

Note 9: ETH::A&D

Deck: ETH::A&D
Note Type: Algorithms
GUID: z{8WPibSbC

added

New Note

Front

Runtime of Dijkstra's Algorithm?

Back

Runtime of Dijkstra's Algorithm?

$O((|E| + |V|) \log |V|)$ (or $O(|V|^2)$

The runtime is calculated from $O(n + (\#\text{extract-min} + \#\text{decrease-key}) \cdot \log n)$ which gives $O((n + m) \cdot \log n)$.

Field-by-field Comparison

Field	Before	After
Name		Dijkstra's Algorithm
Runtime		$O((\|E\| + \|V\|) \log \|V\|)$ (or $O(\|V\|^2)$<br><br>The runtime is calculated from $O(n + (\#\text{extract-min} + \#\text{decrease-key}) \cdot \log n)$  which gives $O((n + m) \cdot \log n)$.
Requirements		No negative edge-weights (to make sure that we don't need to go back)
Approach		Vertices are considered in <i>increasing</i> order of their distances from the source.<br><br>Recurrence:\[ d(s, v_k) = \min_{(v_i, v_k) \in E, i < k} \{ d(s, v_i) + c(v_i, v_k) \} \]<br><ol><li>Add start vertex $s$ to prioqueue with dist 0 and set all other dists to $\infty$</li><li>Pop Cheapest Vertex $v$ from Priority Queue</li><li>For each neighbour $u$: if distance (= current_distance + $w(v\rightarrow u)$) < distance to $u$ then overwrite and push new distance to queue.<br>Current vertex is marked as visited and not revisited again.</li></ol>
Pseudocode		<img src="paste-38d6665cd236d4094cec91025d07594c2e082538.jpg">
Use Case		Cheapest Path in Weighted graph with non-negative edge costs

Tags: ETH::1._Semester::A&D::10._Shortest_Paths::1._Dijkstra's_Algorithm

Note 10: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: q@6d+^{0gK

added

New Note

Front

In Dijkstra's after visiting vertex $v$, the distance $d(v)$ is never updated anymore.

Back

In Dijkstra's after visiting vertex $v$, the distance $d(v)$ is never updated anymore.

No negative edges means there's no shorter way (we consider in increasing distance order).

With negative weights, a longer path through an unvisited vertex could later turn out to be shorter due to a negative edge.

Field-by-field Comparison

Field	Before	After
Text		In Dijkstra's after visiting vertex $v$, the distance $d(v)$ is {{c1:: never updated anymore}}.
Extra		No negative edges means there's no shorter way (we consider in increasing distance order).<br><br>With negative weights, a longer path through an unvisited vertex could later turn out to be shorter due to a negative edge.

Tags: ETH::1._Semester::A&D::10._Shortest_Paths::1._Dijkstra's_Algorithm

Note 11: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Classic
GUID: gm7WcQEU/C

added

New Note

Front

When do we want Dijkstra's with an array?

Back

When do we want Dijkstra's with an array?

In very dense graphs$|E| > \frac{|V|^2}{\log |V|}$, Dijkstra's is faster on an array than in a minHeap.

Extract_min takes $O(|V|)$ with an array ($O(\log |V|)$ in a MinHeap) -> array implementation runtime: $O(|V|^2 + |E|) = O(|V|^2)$ for $|E| = \Theta(|V|^2)$ (there are at most $|V|^2$ edges in a graph).

If we plug in |E| > ... into the log runtime we see it's faster.

Field-by-field Comparison

Field	Before	After
Front		When do we want Dijkstra's with an array?
Back		In very dense graphs$\|E\| > \frac{\|V\|^2}{\log \|V\|}$, Dijkstra's is <b>faster on an array than in a minHeap</b>.<br><br><div>Extract_min takes $O(\|V\|)$ with an array ($O(\log \|V\|)$ in a MinHeap) -> array implementation runtime: $O(\|V\|^2 + \|E\|) = O(\|V\|^2)$ for $\|E\| = \Theta(\|V\|^2)$ (there are at most $\|V\|^2$ edges in a graph).</div><div><br></div><div>If we plug in \|E\| > ... into the log runtime we see it's faster.</div>

Tags: ETH::1._Semester::A&D::10._Shortest_Paths::1._Dijkstra's_Algorithm

Note 12: ETH::A&D

Deck: ETH::A&D
Note Type: Algorithms
GUID: t:15}v~LmN

added

New Note

Front

Runtime of Bellman-Ford?

Back

Runtime of Bellman-Ford?

$O(|V| \cdot |E|)$ (uses DP)

We iterate over all edges in the "relaxation" thus the time complexity of that step is $O(m)$ (the actual check is $O(1)$).
As we relax $n - 1$ (or $n$ for negative cycle check) times, the total runtime is $O(n \cdot m)$.

Field-by-field Comparison

Field	Before	After
Name		Bellman-Ford
Runtime		$O(\|V\| \cdot \|E\|)$ (uses DP)<br><br>We iterate over all edges in the "relaxation" thus the time complexity of that step is $O(m)$ (the actual check is $O(1)$).<br>As we relax $n - 1$ (or $n$ for negative cycle check) times, the total runtime is $O(n \cdot m)$.
Requirements		Negative-edges allowed (neg. cycles detected) in a directed, weighted graph.
Approach		<ol> <li><b>Initialize</b>:<br>Set the distance to the source vertex as 0 and to all other vertices as infinity.</li> <li><b>Relax Edges</b>: <br>Repeat for V − 1 iterations (where V is the number of vertices):<br>For each edge, update the distance to its destination vertex if the distance through the edge is smaller than the current distance.</li> <li><b>Check for Negative Cycles</b>: <br>Check all edges to see if a shorter path can still be found. If so, the graph contains a negative- weight cycle.</li> <li><b>End</b>: <br>If no negative-weight cycle is found, the algorithm outputs the shortest paths.</li></ol><img src="paste-95017d19365697a9f94b52394c6bdb999dfc81d1.jpg"><br><br>(quicker to implement the edge-based approach, but there's also a vertex based approach)
Pseudocode		<img src="paste-46ff4f85bab3ae924d9ef2c955277d49fc616cc6.jpg">
Use Case		Find cheapest path in graphs with negative edges.

Tags: ETH::1._Semester::A&D::10._Shortest_Paths::2._Bellman-Ford_Algorithm

Note 13: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Classic
GUID: o[gwr|.}+m

added

New Note

Front

What is a relaxation in Bellman-Ford?

Back

What is a relaxation in Bellman-Ford?

We "relax" an edge when $d[u] + c(u, v) < d[v]$. In other words, we currently say that there is a path from $s \rightarrow u$ and $u \rightarrow v$ such that it's shorter than $s \rightarrow v$.

This means that our current upper-bound for the shortest distance to $v$ ($d[v]$), is too high as it violates the triangle inequality. Thus we updated ("relax") the edge.

Field-by-field Comparison

Field	Before	After
Front		What is a relaxation in Bellman-Ford?
Back		We "relax" an edge when $d[u] + c(u, v) < d[v]$. In other words, we currently say that there is a path from $s \rightarrow u$ and $u \rightarrow v$ such that it's shorter than $s \rightarrow v$.<br><br>This means that our <b>current upper-bound</b> for the shortest distance to $v$ ($d[v]$), is too high as it violates the triangle inequality. Thus we updated ("relax") the edge.

Tags: ETH::1._Semester::A&D::10._Shortest_Paths::2._Bellman-Ford_Algorithm

Note 14: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Classic
GUID: eoess%f:7$

added

New Note

Front

How does Bellman-Ford detect negative cycles?

Back

How does Bellman-Ford detect negative cycles?

We relax the edges one more time after $n-1$ times. If the distance to an edge decreased, there's a negative cycle reachable from $s$.

Field-by-field Comparison

Field	Before	After
Front		How does Bellman-Ford detect negative cycles?
Back		We relax the edges one more time after $n-1$ times. If the distance to an edge decreased, there's a negative cycle reachable from $s$.

Tags: ETH::1._Semester::A&D::10._Shortest_Paths::2._Bellman-Ford_Algorithm

Note 15: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Classic
GUID: bNHf:CUBWH

added

New Note

Front

Bellman-Ford optimisation in a DAG?

Back

Bellman-Ford optimisation in a DAG?

In an acyclic graph, topological sorting is already an algorithm that gives us the most-efficient order to calculate the cost in.

Because we can be sure that any predecessors already have the correct $l$-good bound distance (guaranteed by topo-sort, no backedges), we can simply relax once.

Thus we can compute the correct cheapest path in one "relaxation": $O(|E|)$.
Therefore with toposort: $O(|V| + |E|)$

Field-by-field Comparison

Field	Before	After
Front		Bellman-Ford optimisation in a DAG?
Back		In an acyclic graph, <b>topological sorting</b> is already an algorithm that gives us the most-efficient order to <b>calculate the cost in</b>.<br><br>Because we can be sure that any predecessors already have the correct $l$-good bound distance (guaranteed by topo-sort, no backedges), we can simply relax once.<br><br>Thus we can compute the correct cheapest path in one "relaxation": $O(\|E\|)$.<br>Therefore with toposort: $O(\|V\| + \|E\|)$

Tags: ETH::1._Semester::A&D::10._Shortest_Paths::2._Bellman-Ford_Algorithm

Field	Before	After
Front		Cost of a walk in a weighted graph \(G = (V, E, c)\):
Back		sum of the weight of it's edges: \(\sum_{i = 0}^{l - 1} c(v_i, v_i+1)\)

Field	Before	After
Text		In Dijkstra's after visiting vertex \(v\), the distance \(d(v)\) is {{c1:: never updated anymore}}.
Extra		No negative edges means there's no shorter way (we consider in increasing distance order).<br><br>With negative weights, a longer path through an unvisited vertex could later turn out to be shorter due to a negative edge.

Note 1: ETH::A&D

Before

Front

Back

After

Front

Back

Note 2: ETH::A&D

Previous

New Note

Front

Back

Note 3: ETH::A&D

Previous

New Note

Front

Back

Note 4: ETH::A&D

Previous

New Note

Front

Back

Note 5: ETH::A&D

Previous

New Note

Front

Back

Note 6: ETH::A&D

Previous

New Note

Front

Back

Note 7: ETH::A&D

Previous

New Note

Front

Back

Note 8: ETH::A&D

Previous

New Note

Front

Back

Note 9: ETH::A&D

Previous

New Note

Front

Back

Note 10: ETH::A&D

Previous

New Note

Front

Back

Note 11: ETH::A&D

Previous

New Note

Front

Back

Note 12: ETH::A&D

Previous

New Note

Front

Back

Note 13: ETH::A&D

Previous

New Note

Front

Back

Note 14: ETH::A&D

Previous

New Note

Front

Back

Note 15: ETH::A&D

Previous

New Note

Front

Back