hw2 graph

Algorithms › 6.006 algorithms

ps5

bfs

1
2
3
4
5
6
7
8
9
10
11
12
13
# bfs
def bfs(Adj, s):
    parent = [None for v in Adj]
    parent[s] = s
    level = [[s]]
    while 0 < len(level[-1]):
        level.append([])
        for u in level[-2]:
            for v in Adj[u]:
                if parent[v] is None:
                    parent[v] = u
                    level[-1].append(v)
    return parent

Analysis:

  1. overall runtime of this bfs: O(|V| + |E|) or O(|E|)

    • inner loop takes O(|E|) time: it cycles through all deg(v) outgoing edges from vertex v.
    • Parent has length |V|

  2. Graph radius

  3. network

    Approach: construct a graph.

    Idea: add an additional node s (a super node) to the graph with an edge to every entry point.

  4. search for connected components

ps6

dfs

  1. topological sort: DAG

    • Simple graph has no self-loops, DAG has no loops

  2. relaxation

    • Tree: In a tree, there is a unique simple path between any pair of vertices, as two distinct simple paths could be used to construct a cycle.

  3. DAG relaxation

  4. Bellman ford: detect loops and negative weight

  5. Input

  6. DAG problem

    • Use DFS to check visiting order is the particular topological order

    • Topological tree has no backward edges/loops.

    • Auxiliary information: index

ps7

  1. Feel smooth when thinking it as water flow.
    • How pq breaks ties may change the visiting order
    • It should be clear how to implement operations.
    • think about connected components （这个图的减小的方式是通过扔掉已经确定是最短路径的点来进行的
  2. negitive weights: detect negative loops
    • connected component C: one vertex can reach any vertex
      • we don’t know if the graph is connected. Likewise, it should be considered if a graph is a DAG/connected/weighted/…(graph’s property)
      • how to find a connected component: considering it is a undirected graph, use DFS/BFS to find C.
    • Whether has negative loops
      • Yes, V in C is -inf, V not in C is inf
      • No, use Dijkstra

reminder

  1. python lambda expression

    1
    lambda x: x**2

  2. Why doesn’t Dijkstra’s algorithm work with non-negative edge weights?

    I think the tight bound is Dijkstra not allowing negative loops that will destroy its minimal property.

Recitation

The problem solving process: transform raw input to IN, apply the algorithm we are familiar with, read raw output to OUT.

Then calculate the runtime and prove for correctness and efficiency.

Bfs

connected components

Dfs

the important part is reasoning process so that we can reason by ourselves to get the answer

edge classification

  • tree edge(dfs traverse)
  • not tree edge
    • Back/forward/cross edge

Problem 1: how this concept relates to dfs?

Problem 1.1: how that defers to undirected graph compared with directed graph?

topological sort -> directed, acyclic, graph

Problem 2: how this concept relates to topological sort?

weighted graph

problem 0: how to build a shortest path algorithm?

simple case: take an edge, split it up, put in fake nodes. Then use bfs

Problem 1: shortest path with odd edges?

比较有趣的是可以把两个状态看成两个平面。

Idea: track state during path building

problem 2: fast way, least fuel. An edge has fixed fuel cost, varying time cost depenTime table Tc (minutes): M = 24*60

Idea: choose a more reasonable state to track and reason carefully.

Bellman-ford

Notice: negative weight

-> detect loops

Dijkstra

Notice: non-negative weight

讲义中分成两部分来看这个算法。整体上看： Dijkstra 像一个流动的水龙头阀门，水流从起点匀速地流动到下一个开关。算法把连续的过程通过 edge relaxation 离散的表示。

  1. Edge relaxation: priority queue -> extract_min/insert/delete

  2. 算法的运行时长与 pq 的具体实现有关。可以从三种角度看：

    存一对 (key, value)， 需要实现三个操作。

    • 当图的点密集时：|E| = Ω(|V|^2) ; direct_access_array; T = O(|V|^2+ |E|)
    • 当图的点稀疏时：|E| = O(|V|) ; heap; T = O((|V |+ |E|) log |V |)
    • 介于两者之间：binary heap; T = O(|V |log |V |+ |E|)

All pairs shortest paths

Runtime: at least O(V^2), because we need find all pairs’ path

naive approach: use n * SSSP algorithms:

  • Using dijkstra for each vertices so as to solve APSP is easy to think but has details to rethink.

Better:

tricky part: how to deal with negative weights?

  1. adgusting edge weights

    problem 1: Are shortest paths still shortest paths?

    • it’s easy to think of adjusting edge weights by adding a large number to each edge weight. But it will base paths with fewer edges.
    • Idea: pick a node u, add 10 to its incoming edges, and subtract 10 from its outgoing edges.

    Problem 2: it’s hard to think a general reweighting functions.

  2. making all wights nonnegative

    Clever choice of reweighting function: Add a new node X with weight-0 directed edges (X, v) for each v ∈V , and choose h(v) = d(X, v).

  3. Johnson’s algorithm is basically two parts: reweighting function then n * dijkstra.

    • the essense is the way to construct a new graph G’ with nonnegative weights:

      Add new vertex X and weight-0 edges (X, v) for all v ∈V as above, and run Bellman-Ford from X to compute h(v) = d(X, v)

    • make sure changing back to G.

      The correct d values in G are d(u, v) = d′(u, v) + h(v) −h(u), and the shortest path trees in G′are also shortest path trees in G

olc

  1. I think the basic idea is date transformation and build intuition about the problems.

  2. why should we know about edge classification…? because it would help to understand the problem better.

  3. Lec 14 notes(19fall) about APSP is worthy reading.

  4. Relaxation: it checks for (u,v) in constructing graph