Homework 2 Flashcards
Formulate optimisation problem as linear program: max x s.t |x| E 0 U [c,d]
x <= d
t = |x|
Max x {
x = a-b
t = a+ b
a <= dz
b <= d(1-z)
t <= dy
t>= cy
a,b>=0 E R
z,y E {0,1}
x E R
Prims algorithm
C(N,Kn) = {all possible roots from start point plus ones not used from the Kn-1 eg if O: OA, OB, OC}
e = smallest number
Kn+1 = {given root so far with single letters: O,B}
Tn = {K4, {given root so far eg: OB}}
general form of the minimal spanning tree problem as a linear programming problem
1) sum of all edges (x_e) = number of nodes - 1
2) sum of edges for each sub graph <= number of edges in sub graph - 1
3) x_e E {0,1} A e E E
Dijkstra algorithm
Let 𝑑 = 0,∞,…,∞ ,𝑝 = (∅,…,∅), and 𝑣 = (0,…,0), denote the distance, previous-node, and visited-node vectors, respectively.
At each iteration:
1. pick the most recently visited node (say node 𝑗)
2. find its neighbouring nodes that have not been visited yet
3. compute the distances to these neighbours assuming the preceding node is 𝑗
4. update the distance and preceding node of these neighbours if passing through node 𝑗 is a shorter path
5. choose a node whose distance is a minimum among the unvisited nodes and mark it as visited. This is the new most recently visited node. Return to step 1 until all nodes are marked as visited.