Network Design Flashcards
Longest and shortest path
1
Q
Greedy Algorithm
A
Makes the best decision “for now”
2
Q
Postoptimality analysis
A
“What if” questions. Change paramater values, see change in result
3
Q
Total weight of a graph
A
Sum of weights of all edges
W(G) = sum(i=1 to q) w(ei)
4
Q
Kruskal’s Algorithm
A
- Pick shortest edge
- From remaining edges, pick shortest edge again (that doesn’t create a cycle)
- Repeat 2 until all vertices are connected
5
Q
Always give 2 answers:
A
Decision variables (ie set of sides) Value of objective function (total weight)
6
Q
Prim’s algorithm
A
- Choose edge with minimum weight
- Add new edge with minimum weight that has 1 edge already selected (must be connected to what you already have)
- Repeat.
- When |S|=n-1, stop
7
Q
Floyd’s Algorithm
A
- Number nodes 1-p and construct distance matrix D^0
- Let k=1
- Calculate new distance matrix D^k with d(jk)=min[d^(k-1) ij, d^(k-1) ik+d^(k-1) kj]
- Determine new values for the predecessor matrix
- Repeat until k=p
8
Q
Longest directed path algorithm
A
LATER
9
Q
Dijkstra’s algorithm
A
- Table with columns for each node with lengths to connecting nodes
- All nodes are part of Bo. Ac is empty
- Mark starting node, Vp, with star and mark with distance 0. Bo = Bo{Vp} and Ac = AcU{Vp}
- Find node with shortest distance from all columns marked with a star. Let this node be V and circle the node with it’s distance (and star). Bo=Bo{V} Ac=AcU{V}
10
Q
Max flow
A
FILL IN
11
Q
Min cost flow
A
Fill in
