Graphs Flashcards
1
Q
What is a graph?
A
A set of vertices and edges. Each edge connects a pair of verticies
2
Q
What is a path in a graph
A
A sequences of vertices connected by edges with no repeated edges
3
Q
What is a simple path in a graph?
A
A path (which is a sequence of vertices connected by edges, with no repeated edges) with no repeated vertices.
4
Q
What is a cycle in a graph?
A
A path (which is a sequence of vertices connected by edges, where no edge is repeated) with at least one edge. The path’s first and last vertices are the same.
5
Q
What is a simple cycle?
A
A cycle (which is a path with at least one edge whose first and last vertices are the same, and where a path is a sequence of vertices connected by edges with no repeated edges) with no repeated vertices. Note that the first and last vertices will be the same.
6
Q
What is the length of a cycle or path in a graph?
A
It is the number of edges in a path (vertices connected by edges with no repeated vertices) or a cycle (path with at least one edge whose first and last vertices are the same).
7
Q
What is a connected graph?
A
A graph that contains a path (vertices with no rotated edges) between all vertices.
8
Q
Describe a tree in terms of a graph
A
An acyclic connected graph (or a graph with no cycles and where every vertex has a path to every other vertex)
9
Q
What is a spanning tree of a connected graph?
A
A connected graph is a graph that contains a path from every vertex, to every other vertex. The spanning tree is a subgraph that contains all the vertices of the connected graph. The subgraph is a tree (acyclic and connected graph)
10
Q
Describe how a depth first search algorithm visits the vertices of a graph
A
When visiting a vertex
- Mark it as visited
- Visit (recursively) all the vertices that are adjacent to it and that have not yet been marked
11
Q
What is the time complexity of DFS when marking all nodes?
A
The time complexity is proportional to the sum of all vertices degrees.
12
Q
Write a simple DFS algorithm that searches each vertex.
A
private void dfs(int source) {
marked[source] = true;
count++;
for(int w : adj.get(source))
if (!marked[w]) dfs(w)
13
Q
Name two problems DFS can solve when looking at graphs
A
Connectivity: are two different vertices connected? How many connected components does a graph have?
Single-source paths: find a path from source vertex to target vertex
14
Q
Write a simple DFS algorithm that finds paths from a source to all vertices
A
Utilize an array called edgeTo[], where edgeTo[w] = v indicates that v-w edge accesses w first in the path. The array is a parent-link representation of the tree rooted at the source. Said another way v is the parent of w.
Private void dfs(int s) {
marked[v] = true;
for (int w : adj.get(s)) {
if (!marked[w]) {
edgeTo[w] = s;
dfs(w);
}
}
}
15
Q
What is the time complexity of a depth first search algorithm providing a path from a source vertex to a target vertex?
A
The time complexity is equal to the length of the path.
16
Q
Name one problem breadth first search solves
A
This algorithm solves the single-source shortest paths problem. This is equivalent to finding the shortest path (path with fewest edges) from source to some vertex.
17
Q
How does breadth first search visit each vertex?
A
This algorithm visits each graph vertex by:
Remove the next vertex from the queue
Put onto the queue all unmarked vertices that are adjacent to the vertex and mark them as seen.
18
Q
Write a breadth first search algorithm that visits all nodes and records a path from a source to all vertices
A
Utilize the edge to array to record each vertices parent vertex. Each vertex in the graph is visited first from their parent vertex.
private void bfs(int s) {
Queue<Integer> queue = new Queue<Integer>();
marked[s] = true;
while(!queue.isEmpty()) {
int v = queue.dequeue();
for(int w : adj.get(v)) {
if (!marked[w]) {
edgeTo[w] = v;
marked[w] = true;
queue.enqueue(w);
}
}
}</Integer></Integer>
}
19
Q
Write a breadth first search algorithm that visits all nodes and records a path from a source to all vertices
A
Utilize the edge to array to record each vertices parent vertex. Each vertex in the graph is visited first from their parent vertex.
private void bfs(int s) {
Queue<Integer> queue = new Queue<Integer>();
marked[s] = true;
while(!queue.isEmpty()) {
int v = queue.dequeue();
for(int w : adj.get(v)) {
if (!marked[w]) {
edgeTo[w] = v;
marked[w] = true;
queue.enqueue(w);
}
}
}</Integer></Integer>
}
20
Q
Which graph algorithm finds the shortest path from source vertex s to all vertices?
A
The breadth first search algorithm finds these paths within a graph
21
Q
What is the worst case time complexity of breadth first search?
A
The worst case time complexity of this graph algorithm is Edges+Vertices
22
Q
What is the worst case time complexity of breadth first search?
A
The worst case time complexity of this graph algorithm is Edges+Vertices
23
Q
How can you modify the depth first search algorithm to determine if two vertices are connected?
A
Modify the depth first search algorithm by assigning a count or id value to every source vertex passed to the DFS method. The count value is a class instance variable. The DFS method is called for every vertex in the graph that has not been marked (visited) yet. Every time a DFS is called, increase the instance count value. This will ensure that every vertex that is reached by the DFS algorithm will be assigned to the same id value. Therefore, all vertices within the same subgraph will have the same id.
24
Q
How could you modify a simple depth first search algorithm to determine if a graph contains a cycle? Assume the graph has no loops nor any parallel edges.
A
Modify the depth first search algorithm to check if any adjacent vertices are marked but not the source’s parent vertex. If this is true, set a boolean flag equal to true. When calling the depth first search algorithm, pass the adjacent vertex as the source vertex to examine next, along with the current vertex under investigation as the parent to the source vertex.
25
How could you modify a simple depth first search algorithm to determine if a graph is two-colorable (bipartite)? Said another way, can you assign two colors to every vertex in the graph such that two adjacent vertices don't have the same color?
Modify the depth first search algorithm to assign a color to all adjacent vertices that are not marked, with the color opposite of the current vertices color. For marked adjacent vertices, check that the color of the current vertex is different from the color of the adjacent vertex. If not, set the boolean flag to false. Return this boolean flag.
26
Compare and contrast the marking strategy of the breadth first search algorithm and the depth first search algorithm.
The breadth first search algorthim must mark
27
What is a directed graph or digraph?
A set of vertices and directed edges. Where each directed edge connects one vertex with another vertex in a particular direction.
28
What is a directed path?
A sequence of vertices in a digraph with each vertex in the sequence contains a directed edge point from it to its successor. There are no repeated edges.
29
What is a simple directed path?
A directed path with no repeated vertices.
30
What is a directed cycle?
A directed path with at least one edge whose first and last vertices are the same
31
What is a simple directed cycle?
A directed cycle with no repeated vertices (except the requisite repetition of the first and last vertices).
32
How does depth first search change when solving the reach ability problem (is there a directed path from some source vertex to a target vertex) for a digraph?
There is no change. Instead, the adjacency list which captures all adjacent vertices for each vertex is no longer symmetric.
33
How does depth first search and breadth first search algorithms change when finding paths in digraphs (compared with undirected graphs)?
There is no change and these methods can solve for single-source directed path (is there a directed path from a source to a target vertex) and single source shortest directed path (if there is a directed path, find the shortest path between source and target vertex).
34
Define what a topological sort is in relation to a digraph
Order vertices such that directed edges point towards vertices that are farther down in the order. If vertex a points towards vertex b, vertex b must come after vertex a. If you displayed the vertices in order, in a line, from left to right. All edges would point towards the right.
35
What is a directed acyclic graph?
A digraph with no directed cycles.
36
What type of problems require no cycles in a digraph in order to solve?
If a schedule is represented by a directed graph, where each job must cannot be completed prior to other jobs, (precedence-constrained scheduling) then the graph cannot have cycles. Essentially, if the graph constrains the order vertices are processed, there cannot be loops because there is no start and no end.
37
If you traverse a graph using depth first search the vertices that are visited are marked. Can you utilize this information to determine if a cycle exists in a graph?
For undirected graphs, this information can be used to detect cycles in a graph. If a vertex is marked, it has a path to all other marked vertices in the graph. Therefore, if the current vertex has a marked adjacent vertex, a path already exists between these two vertices. A second path would introduce a cycle. Note, however, that the parent node (the node used to mark the current node) is connected to the current node through the path that is currently under investigation. Therefore, it cannot be used to detect cycles
Directed graphs can not use this information. While mark vertices are indications that a vertex has been visited, we cannot say which directed path(s) contain this vertex. For a directed cycle to occur, we need a directed path with the last vertex equal to the first vertex. This is why it is important to record the current path's vertices. If you encounter any of the current path's vertices again, you have a cycle.
38
Depth first search avoids searching vertices twice by marking them as seen or marked. Does this prevent us from seeing paths that may contain cycles?
No, in the undirected case, encountering an adjacent marked vertex that is not the current vertex's parent is an indication that the graph has a cycle.
For directed graphs, if the current directed path pursued by the DFS is stopped by a marked vertex, it is impossible for that vertex to contribute to a cycle unless it is in the current call stack. This is because a path is terminated once no more unmarked adjacent vertices are available. If your current vertex was not encountered, it was not apart of this vertex's path.
39
If a path exists from vertex s to vertex v, does a path exist from v to s?
For undirected graphs, yes. For directed graphs, not necessarily. This is why we have directed paths in directed graphs.
40
Implement directed cycle detection for a digraph. It should record a path containing a cycle if one exists.
Utilize, marked array to record vertices that are visited. Utilize edgeTo array to record each vertice's parent vertex (the vertex that first visited and marked edgeTo[v] vertex v). Utilize a stack to store the directed path containing the cycle. Utilize the onStack array to record the vertices in the current recursion stack. This is equivalent to the vertices in the current directed path.
Note, to check the entire graph, apply this DFS method to all nodes who are not marked.
private void dfs(int v) {
onStack[v] = true
marked[v] = true
for (int w : adj.get(g)) {
if (cycle != null) return
else if (!marked[w])
{ edgeTo[w] = v; dfs(w); }
else if (onStack[w])
{
cycle = new Stack<>();
for (int x = v; x != w; x = edgeTo[x])
cycle.push(x);
cycle.push(w);
cycle.push(v);
}
onStack[v] = false;
}
}
41
What prevents a graph from having topological order?
A directed cycle or a digraph with loop will not allow for this type of its vertices.
42
What prevents a graph from having topological order?
A directed cycle or a digraph with loop will not allow for this type of its vertices.
43
What is reverse postorder in a depth first search algorithm
An order of vertices in a graph that is equivalent to the topological order of the graph. Vertices are put onto a stack after a recursive call is made.
44
Write an algorthim that returns the vertices in a topologically sorted manner.
Utilize the depth first search algorithm. Capture vertices in reverse post order by saving them to a stack after the recursion call. Note that this algorthim assumes a digraph. Check for cycles prior to using.
private void dfs(int v) {
marked[v] = true;
for (int w : adj.get(v)) {
if (!marked[w]) dfs(w);
}
reversePost.push(v);
}
45
Why does reverse postorder in depth first search produce a topologically sorted list of vertices?
for an edge V->W, when dfs(V) is called, only three scenarios are allowed
dfs(w) has already been called and has returned (w is marked)
dfs(w) has not been called and will be called (w is unmarked). The fire, dfs(w) comes before dfs(v)
dfs(w) has been called but has not returned. This can only happen when a cycle exists (there is another path from v to w).
If there is no cycle, dfs(w) finishes before dfs(v). Reversed post order will place dfs(w) on the stack before dfs(v) causing v to always come before w. This is why confirming that a cycle is not present before dfs based topological sort is important.
46
What does it mean if two vertices are strong connected in a digraph.
The two vertices are mutually reachable. A directed path exists from the first vertex to the second vertex, and from the second vertex to the first vertex.
47
What does it mean for a digraph to be strongly connected?
A graph where all of its vertices are strongly connected to one another
48
What is a strongly connected component?
A subgraph that is strongly connected
49
What is the time complexity of a depth first search based algorithm for determining topological order!
The time complexity is E + V where E is the number of edges and V is the number of vertices.
50
Summarize the steps taken to group vertices in a graph into strongly connected components (Kosaraju-Sharir Algorithm)
Calculate the reverse postorder of the reversed digraph (the original digraph but with its edges reversed) using depth first search
Perform depth first search on the digraph, but check the vertices in the order dictated by the reverse postorder of the reverse digraph
While iterating over the list of vertices whose order is outline by the reverse postorder in the reversed digraph, each vertex will be searched using depth first search if and only if the vertex is unmarked. An unmarked vertex indicates the beginning of a strongly connected component. All vertices visited during the depth first search are in the same strongly connected component.
51
Utilize a modified depth first search algorithm to find connected components of a graph
Connected components apply to undirected graphs. Depth first search will be applied to each vertex of the graph that is unmarked. An unmarked vertex indicates a new component of the graph. Count these components and use the count value as an id for all components in the graph that are in the same component
for (int s = 0; s < V; s++) {
if (!marked[s]) { dfs(s); count++}
}
private void dfs(int v) {
marked[v] = true;
id[v] = count;
for (int w : adj.get(v)) {
dfs(w);
}
}
52
What is the difference between an algorithm finding strongly connected components of a digraph and an algorithm finding connected components of an undirected graph?
Both algorithms check every vertex to determine how many components exist within the the graph. An undirected graph does not care about the order of the vertices while a digraph must search vertices in a specific order (reverse postorder of the reversed digraph). In both cases, encountering an unmarked vertex indicates a new component.
53
Given a subgraph of G called C, and a vertex of G but not in C called v. If there is an edge from any vertex in C pointing to v, how will the reverse postorder of G reversed order v and all vertices in C?
The vertex v will appear before every vertex in C if an edge exists between any vertex in C to v in this list.
54
If we visit each vertex in order dedicated by the reverse postorder of the reversed digraph, why will a depth first search stay contained with the strongly connected component?
Because of the Oder of the vertices, strongly connected components accessible by the current component will already be marked. All other components will be unreachable.
55
What is the time complexity of the Kosaraju-Sharir algorithm (the algorithm that determines the strongly connected components of a graph.
The time complexity is equal to number of edges plus number of vertices.
56
What is a minimum spanning tree of an edge-weighted graph?
A spanning tree whose weight (the sum of the weights of its edges) is no larger the weight of any other spanning tree.
57
What two properties of a tree are fundamental for solving for the minimum spanning tree?
The two properties of trees that are fundamental to this algorithm are
(1) adding an edge to two nodes of a tree introduces a unique cycle
(2) removing an edge from a tree breaks the tree into two trees.
58
What is a cut of a graph?
A partition of the graph vertices into two nonempty, disjoint sets.
59
What is a cut of a graph?
A partition of the graph vertices into two nonempty, disjoint sets.
60
What is a crossing edge of a cut?
An edge that connects a vertex in one set with a vertex in the other.
61
What is the relationship between the crossing edge of a cut and the minimum spanning tree of a weight graph?
The crossing edge of minimum weight is in the minimum spanning tree.
62
Describe Prim's algorithm in words
The algorithm finds the minimum spanning tree of any connected edge-weight graph by building the MST one edge at time. To determine the next edge, it picks the smallest weigh edge connecting the vertices on the tree with the vertices not on the tree (this is the cross edge of the cut containing the MST). Care should be taken to find the minimum edge efficiently.
63
Implement a lazy version of Prim's algorithm
Utilize a priority queue to keep track of the minimum weighted edge. Add added as you encounter vertices. If the minimum edge is disallowed because both vertices are marked as being in the MST, remove from the stack.
private boolean[] marked;
private Queue mst;
private PriorityQueue pq;
public class Edge implements Comparable{
int weight;
int v;
int w;
public double either(){
return v;
}
public int other (int vertex) {
if (vertex == v) return w;
else return v;
}
public int compareTo(Edge that) {
if (this.weight < that.weight) return -1;
else if (this.weight > that.weight) return 1;
else return 0;
}
}
public void LazyPrimMST() {
pq = new PriorityQueue<>((a,b)->(a.weight -b.weight));
marked = new boolean[V];
mst = new LinkedList<>();
visit(0);
while (!pq.isEmpty()) {
Edge e = pq.poll();
int v = e.either(); int w = e.other(v);
if(marked[v] && marked[w]) continue;
mst.add(e);
if (!marked[v]) visit(v);
if(!marked[w]) visit(w);
}
}
private void visit(int v) {
marked[v] = true;
for (Edge e : adj.get(v)) {
if (!marked[e.other(v)]) pq.insert(e);
}
}
64
What is the time and space complexity of Prim's algorithm with lazy implementation
The time complexity is E log E (worst case) and space equal to E where E is the number of edges. This is determined by the priority queue.
65
Describe how the eager version of Prim's algorithm reduces the number of vertices on the queue compared to the lazy version of Prim's algorithm
The algorithm maintains only one edge per non tree vertex on the priority queue. When visiting a non tree vertex, only the minimum vertex connecting vertex with tree is kept.
This is possible because the minimum crossing edge of min weight must be in the minimum spanning tree. All other edges will be removed evetually.
66
Describe Kruskal's Algorithm
Sort the edges in ascending order based on their weight values. Add the edges in order so long as it doesn't introduce a loop. Stop once you have V-1 edges where V is the number of vertices in the tree. The edges constitute the minimum spanning tree of the graph
67
What is the shortest-path tree in an edge weighted digraph?
A subgraph containing the source vertex and all the vertices reachable by the source that forms a directed tree rooted at the source. Every tree path is a shortest path.
68
Name two useful data structures for determining the shortest path in weighted digraphs
Edges on shortest-path tree: use a vertex indexed array to represent parent-edges. The array stores directed edge objects. EdgeTo[v] = is the edge that connects vertex v with the tree
Distance to source: vertex indexed array that stores the shortest path distance from source to the vertex.
69
Describe Edge Relaxation
Let's say we are investigating an edge from v to w. We want to know if the edge v->w lies on the shortest path from the source vertex s, to the vertex w. Calculate a new shortest distance for w by taking the distance from the current shortest distance from a to v (distTo[v]) and add the weight value for the edge v->w to it. If it's less than the current minimum distance to w, update it!
70
Describe vertex relaxation.
Relax all edges leaving a given vertex. The relaxation process updates both the distTo data structure and edgeTo data structure for all eligible terminating vertices
71
Describe the shortest path optimality condition
Assume we have a digraph with weighted edges. Select a source vertex s with the goal of determining the shortest weighted distance between s and some vertex v in the graph. If we record path lengths within a vertical indexed array called distTo[v], all values in distTo[v] is equal to the shortest path from s to v if and only if distTo[w] <= distTo[v] + edgeWeight(v,w). Where edgeWeight(v,w) is the edge weight for edge going from v to some connected edge w. For distTo[s], the value is equal to zero. For unreachable vertices, the distTo will equal infinity.
To interpret the results, imagine there is a path from s to w that is larger then the path from s to v plus the edge weight from v to w. This would indicate that the shortest path for w is incorrect.
We now have a way to test the validity of the distTo result of any algorithm.
72
Describe the shortest path optimality condition
Assume we have a digraph with weighted edges. Select a source vertex s with the goal of determining the shortest weighted distance between s and some vertex v in the graph. If we record path lengths within a vertical indexed array called distTo[v], all values in distTo[v] is equal to the shortest path from s to v if and only if distTo[w] <= distTo[v] + edgeWeight(v,w). Where edgeWeight(v,w) is the edge weight for edge going from v to some connected edge w. For distTo[s], the value is equal to zero. For unreachable vertices, the distTo will equal infinity.
To interpret the results, imagine there is a path from s to w that is larger then the path from s to v plus the edge weight from v to w. This would indicate that the shortest path for w is incorrect.
We now have a way to test the validity of the distTo result of any algorithm.
73
Describe Dijkstra's algorithm in words
The algorithm determines the shortest path from a given source vertex to any reachable vertex in the graph. It utilizes the distTo vertex indexed array to record the shortest path (or really, the best shortest path at this point in time). Set the source vertex distTo to zero and all other vertices to positive infinity. Relax the vertex of the non-tree vertex with the smallest distTo value and add the vertex to the shortest path tree. Continue until all vertices are all on the tree or all non-tree vertices have infinite distance.
74
Implement Dijkstra's algorithm
Utilize the distTo and edgeTo vertex indexed arrays to track the minimum distance to source and the parent vertex, respectively of each vertex in the graph. The reachable vertices within the edgeTo array correspond to a shortest path tree. Utilize a priority queue pq to relax all candidate vertices next.
public class DijkstraSP {
private DirectedEdge[] edgeTo;
private double[] distTo;
private IndexMinPQ pq;
public DijkstraSP(EdgeWeightedDigraph G, int s) {
edgeTo = new DirectedEdge[G.V()];
distTo = new double[G.V()];
pq = new IndexMinPQ pq;
for (int v = 0; v < G.V(); v++) {
distTo[v] = Double.POSITIVE_INFINITY;
}
distTo[s] = 0.0;
pq.inserts(s, 0.0);
while(!pq.isEmpty()) {
relax(G, pq.delMin()); //
}
private void relax(EdgeWeightedDigraph G, int v) {
for (DirectedEdge e : G.adj(v)) {
int w = e.to();
if (distTo[w] > distTo[v] + e.weight()){
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;
if (pq.contains(w)) pq.changeKey(w, distTo[w]);
else pq.insert(w, distTo[w]);
}
}
}
}
}
75
What is the time and space complexity of the Dijkstra's algorithm
The space complexity is O(V) and the time complexity is O(E log V) (worst case) where V is the number of vertices and E is the number of edges of the graph.
76
Compare Prim's algorithm with Dijkstra's algorithm
Both algorithms build a tree by adding one edge and one vertex to the tree at a time. One is utilized for undirected weight graphs while the other is used for weighted digraphs. The undirected algorithm builds the tree by adding the vertex closest to the tree, while the directed graph builds the tree by finding the vertex closest to the source. In the undirected graph, a marked array is needed. In the directed graph the distTo not being infinity is equivalent to a marked vertex.
77
78
Compare the Dijkstra algorithm with a shortest path algorithm that utilizes the graph's topological order.
1. The topological sort based algorithm solves for the shortest path in linear time (E + V) as opposed to E log V
2. The topological sort based approach can handle negative weights while Dijkstra requires nonnegative weights
3. The topological sort based algorithm can find longest path
79
Describe an algorithm that utilizes topological order to find the shortest path in an edge weighted acyclic digraph
Relax vertices in topological order. The distance to source is set to zero while to all others it's set to infinity.
80
Implement a shortest path algorithm for an acyclic digraph with weighted edges using topological sort
public class AcyclicSP {
private DirectedEdge[] edgeTo;
private double[] distTo;
public AcyclicSP(EdgeWeightedDigraph G, int s) {
edgeTo = new DirectedEdge[G.V()];
distTo = new double[G.V()];
for(int v = 0; v < G.V(); v++) {
distTo[v] = Double.POSITIVE_INFINITY;
}
distTo[s] = 0.0;
Topological top = new Topological(G);
for(int v: top.order()) relax(G, v);
}
private void relax(EdgeWeightedDigraph G, int v) {
for(DirectedEdge e : G.adj(v)) {
int w = e.to();
if (distTo[w] > distTo[v] + e.weight()) {
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;
}
}
}
}
81
Describe how to modify a topological sort based shortest path algorithm for acyclic digraphs with weighted edges to produce the longest path
Negate the weights of the graph and determine the shortest path. Note that negative weight values are allowed in this algorithm.
82
Describe parallel precedence-constrained scheduling
This is a scheduling algorithm where you assume you have infinite workers to handle jobs with a specified duration. The jobs are constrained by precedence. Said another way, some jobs come before other jobs. The jobs may be performed in parallel but must adhere to the precedence constraint. The scheduling algorithm aims to find a schedule with the minimum total time.
83
84
Describe the parallel precedence-constrained scheduling problem
Let's say we have jobs that each take a certain amount of time. They are constrained by precedence or some must occur before others. How quickly can we complete all jobs assuming we can do as many jobs as we want at once?
85
How do you solve for the critical path of a parallel precedence-constrained scheduling problem?
Represent the problem using an acyclic digraph. Each job is represented by two nodes connected by a weighted edge whose value equal's the job's duration. Jobs that depend on one another are connected with edges equal to zero weight. Add a source vertex and a sink vertex. The source vertex is connected to every job's start node. The sink to every job's end node. All edges are zero-weight. It then calculates the longest path in the graph and returns the total time.
86
Give the time complexity of the critical path method used to solve parallel precedence-constrained scheduling.
The time complexity is linear or E + V
87
What is parallel job scheduling with relative deadlines?
This is a job scheduling problem that contains precedence constrains and deadline constraints. To meet the deadline constraint, jobs must begin with in a certain amount of time relative to the start time of another job.
88
How do you solve the parallel job scheduling with relative deadlines problem?
Each job is represented by a start and end node. The weight of the edge connecting each node is weighted to equal the job's duration. The start node points to each start node and the sync node points to each node node. These edges are zero weighted. Precedence is also captured by zero weighted edges.
If a job with terminations node v has to start within d time units after a job with starting node w, make an edge from v to w with negative weight equal to -d. Negate all weights and solve for the shortest path. This only works if the schedule is feasible.
