Depression and Major Depressive Disorder
Depression is a mood disorder that impacts thoughts, emotions, and behaviors, causing feelings of sadness and hopelessness. Major Depressive Disorder (MDD) is a severe form of depression affecting millions of adults and children, with symptoms like persistent sadness, loss of interest, appetite changes, and thoughts of suicide. Factors such as genetics, stress, biochemical reactions, and hormone imbalances can contribute to MDD. Studies show changes in brain activity and shape associated with severe mood disorders, highlighting areas like the hippocampus and frontal lobes. Early diagnosis and understanding of MDD are crucial for effective management and treatment.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CSCE-411 Design and Analysis of Algorithms Spring 2025 Instructor: Jianer Chen Office: PETR 428 Phone: 845-4259 Email: chen@cse.tamu.edu Notes 25: Minimum spanning tree: Prim s Algorithm
All-Pairs Shortest Paths (APSP) Problem. Given a (possibly negatively) weighted graph G, find the shortest path from s to t for all vertex pairs (s, t). Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. Johnson s APSP Algorithm(G) 1. construct the graph G+ by adding the vertex z and all edges from z; 2. use Bellman-Ford to compute dist+(z, v) in G+ for all vertices v, and let h(v) = dist+(z, v); 3. construct the graph G by reweighting edges [u, v] in G+: wt (u, v)=wt+(u, v)+h(u) h(v); 4. use Dijkstra to solve the APSP problem for G ; 5. Get the APSP solution to G. -2 The graph G -1 -3 4 3 1 1 1 4
All-Pairs Shortest Paths (APSP) Problem. Given a (possibly negatively) weighted graph G, find the shortest path from s to t for all vertex pairs (s, t). Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. Johnson s APSP Algorithm(G) 1. construct the graph G+ by adding the vertex z and all edges from z; 2. use Bellman-Ford to compute dist+(z, v) in G+ for all vertices v, and let h(v) = dist+(z, v); 3. construct the graph G by reweighting edges [u, v] in G+: wt (u, v)=wt+(u, v)+h(u) h(v); 4. use Dijkstra to solve the APSP problem for G ; 5. Get the APSP solution to G. -2 The graph G+ 0 -1 -3 4 3 0 1 1 0 0 1 0 4 z 0
All-Pairs Shortest Paths (APSP) Problem. Given a (possibly negatively) weighted graph G, find the shortest path from s to t for all vertex pairs (s, t). Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. Johnson s APSP Algorithm(G) 1. construct the graph G+ by adding the vertex z and all edges from z; 2. use Bellman-Ford to compute dist+(z, v) in G+ for all vertices v, and let h(v) = dist+(z, v); 3. construct the graph G by reweighting edges [u, v] in G+: wt (u, v)=wt+(u, v)+h(u) h(v); 4. use Dijkstra to solve the APSP problem for G ; 5. Get the APSP solution to G. -3 -1 -2 The graph G+ 0 -1 -3 4 3 0 0 0 1 1 0 0 0 1 0 4 z 0 0 0
All-Pairs Shortest Paths (APSP) Problem. Given a (possibly negatively) weighted graph G, find the shortest path from s to t for all vertex pairs (s, t). Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. Johnson s APSP Algorithm(G) 1. construct the graph G+ by adding the vertex z and all edges from z; 2. use Bellman-Ford to compute dist+(z, v) in G+ for all vertices v, and let h(v) = dist+(z, v); 3. construct the graph G by reweighting edges [u, v] in G+: wt (u, v)=wt+(u, v)+h(u) h(v); 4. use Dijkstra to solve the APSP problem for G ; 5. Get the APSP solution to G. -3 -1 0 -2 The graph G 0 3 6 4 0 -1 1 -3 3 4 0 0 0 1 1 1 1 1 0 0 0 0 0 1 0 1 0 4 4 z 0 0 0 0
All-Pairs Shortest Paths (APSP) Problem. Given a (possibly negatively) weighted graph G, find the shortest path from s to t for all vertex pairs (s, t). Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. Johnson s APSP Algorithm(G) 1. construct the graph G+ by adding the vertex z and all edges from z; 2. use Bellman-Ford to compute dist+(z, v) in G+ for all vertices v, and let h(v) = dist+(z, v); 3. construct the graph G by reweighting edges [u, v] in G+: wt (u, v)=wt+(u, v)+h(u) h(v); 4. use Dijkstra to solve the APSP problem for G ; 5. Get the APSP solution to G. -3 -1 0 The graph G 0 3 6 4 1 0 0 1 1 1 0 0 0 0 1 4 z 0 0 0
All-Pairs Shortest Paths (APSP) Problem. Given a (possibly negatively) weighted graph G, find the shortest path from s to t for all vertex pairs (s, t). Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. Johnson s APSP Algorithm(G) 1. construct the graph G+ by adding the vertex z and all edges from z; 2. use Bellman-Ford to compute dist+(z, v) in G+ for all vertices v, and let h(v) = dist+(z, v); 3. construct the graph G by reweighting edges [u, v] in G+: wt (u, v)=wt+(u, v)+h(u) h(v); 4. use Dijkstra to solve the APSP problem for G ; 5. Get the APSP solution to G. -3 -1 0 The graph G 0 3 6 4 1 0 0 1 1 1 0 0 0 0 1 4 z 0 0 0
All-Pairs Shortest Paths (APSP) Problem. Given a (possibly negatively) weighted graph G, find the shortest path from s to t for all vertex pairs (s, t). Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. Johnson s APSP Algorithm(G) Time O(n) 1. construct the graph G+ by adding the vertex z and all edges from z; 2. use Bellman-Ford to compute dist+(z, v) in G+ for all vertices v, and let h(v) = dist+(z, v); 3. construct the graph G by reweighting edges [u, v] in G+: wt (u, v)=wt+(u, v)+h(u) h(v); 4. use Dijkstra to solve the APSP problem for G ; 5. Get the APSP solution to G. -2 The graph G+ 0 -1 -3 4 3 0 1 1 0 0 1 0 4 z 0
All-Pairs Shortest Paths (APSP) Problem. Given a (possibly negatively) weighted graph G, find the shortest path from s to t for all vertex pairs (s, t). Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. Johnson s APSP Algorithm(G) Time O(n) 1. construct the graph G+ by adding the vertex z and all edges from z; 2. use Bellman-Ford to compute dist+(z, v) in G+ for all vertices v, and let h(v) = dist+(z, v); 3. construct the graph G by reweighting edges [u, v] in G+: wt (u, v)=wt+(u, v)+h(u) h(v); 4. use Dijkstra to solve the APSP problem for G ; 5. Get the APSP solution to G. -3 -1 -2 The graph G+ O(nm) Also check negative cycles 0 -1 -3 4 3 0 0 0 1 1 0 0 0 1 0 4 z 0 0 0
All-Pairs Shortest Paths (APSP) Problem. Given a (possibly negatively) weighted graph G, find the shortest path from s to t for all vertex pairs (s, t). Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. Johnson s APSP Algorithm(G) Time O(n) 1. construct the graph G+ by adding the vertex z and all edges from z; 2. use Bellman-Ford to compute dist+(z, v) in G+ for all vertices v, and let h(v) = dist+(z, v); 3. construct the graph G by reweighting edges [u, v] in G+: wt (u, v)=wt+(u, v)+h(u) h(v); 4. use Dijkstra to solve the APSP problem for G ; 5. Get the APSP solution to G. -3 -1 0 The graph G O(nm) Also check negative cycles 0 3 6 4 1 0 0 1 1 1 0 0 O(m) 0 0 1 4 z 0 0 0
All-Pairs Shortest Paths (APSP) Problem. Given a (possibly negatively) weighted graph G, find the shortest path from s to t for all vertex pairs (s, t). Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. Running Dijkstra n times, each for a vertex v, taking time O(nm log n). For each vertex v in G , we keep the dist v[1..n] array for distances from v to all other vertices, and the dad v[1..n] array that lets tracing the shortest paths from v (backwards). This takes space O(n2). Johnson s APSP Algorithm(G) Time O(n) 1. construct the graph G+ by adding the vertex z and all edges from z; 2. use Bellman-Ford to compute dist+(z, v) in G+ for all vertices v, and let h(v) = dist+(z, v); 3. construct the graph G by reweighting edges [u, v] in G+: wt (u, v)=wt+(u, v)+h(u) h(v); 4. use Dijkstra to solve the APSP problem for G ; 5. Get the APSP solution to G. O(nm) Also check negative cycles O(m) O(nm log n)
All-Pairs Shortest Paths (APSP) Problem. Given a (possibly negatively) weighted graph G, find the shortest path from s to t for all vertex pairs (s, t). Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. Running Dijkstra n times, each for a vertex v, taking time O(nm log n). For each vertex v in G , we keep the dist v[1..n] array for distances from v to all other vertices, and the dad v[1..n] array that lets tracing the shortest paths from v (backwards). This takes space O(n2). Johnson s APSP Algorithm(G) Time O(n) 1. construct the graph G+ by adding the vertex z and all edges from z; 2. use Bellman-Ford to compute dist+(z, v) in G+ for all vertices v, and let h(v) = dist+(z, v); 3. construct the graph G by reweighting edges [u, v] in G+: wt (u, v)=wt+(u, v)+h(u) h(v); 4. use Dijkstra to solve the APSP problem for G ; 5. Get the APSP solution to G. O(nm) Also check negative cycles O(m) From the arrays dist v[1..n] and dad v[1..n] for all vertices v, we can build the distance matrix Dist[1..n, 1..n] and Previous-Vertex matrix Pre[1..n, 1..n] for the APSP problem for the original graph G: Dist[u, v] = dist u[v] h(u) + h(v), and Pre[u, v] = dad u[v]. This takes time O(n2). O(nm log n) O(n2)
All-Pairs Shortest Paths (APSP) Problem. Given a (possibly negatively) weighted graph G, find the shortest path from s to t for all vertex pairs (s, t). Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. Running Dijkstra n times, each for a vertex v, taking time O(nm log n). For each vertex v in G , we keep the dist v[1..n] array for distances from v to all other vertices, and the dad v[1..n] array that lets tracing the shortest paths from v (backwards). This takes space O(n2). Johnson s APSP Algorithm(G) Time O(n) 1. construct the graph G+ by adding the vertex z and all edges from z; 2. use Bellman-Ford to compute dist+(z, v) in G+ for all vertices v, and let h(v) = dist+(z, v); 3. construct the graph G by reweighting edges [u, v] in G+: wt (u, v)=wt+(u, v)+h(u) h(v); 4. use Dijkstra to solve the APSP problem for G ; 5. Get the APSP solution to G. O(nm) Also check negative cycles O(m) From the arrays dist v[1..n] and dad v[1..n] for all vertices v, we can build the distance matrix Dist[1..n, 1..n] and Previous-Vertex matrix Pre[1..n, 1..n] for the APSP problem for the original graph G: Dist[u, v] = dist u[v] h(u) + h(v), and Pre[u, v] = dad u[v]. This takes time O(n2). O(nm log n) O(n2) Time = O(nm log n), space = O(n2)
All-Pairs Shortest Paths (APSP) Problem. Given a (possibly negatively) weighted graph G, find the shortest path from s to t for all vertex pairs (s, t). Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. Johnson s APSP Algorithm(G) Theorem. The All-Pairs Shortest Path problem (APSP) can be solved in time O(nm log n) and space = O(n2). 1. construct the graph G+ by adding the vertex z and all edges from z; 2. use Bellman-Ford to compute dist+(z, v) in G+ for all vertices v, and let h(v) = dist+(z, v); 3. construct the graph G by reweighting edges [u, v] in G+: wt (u, v)=wt+(u, v)+h(u) h(v); 4. use Dijkstra to solve the APSP problem for G ; 5. Get the APSP solution to G. Time = O(nm log n), space = O(n2)
All-Pairs Shortest Paths (APSP) Problem. Given a (possibly negatively) weighted graph G, find the shortest path from s to t for all vertex pairs (s, t). Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. Johnson s APSP Algorithm(G) Theorem. The All-Pairs Shortest Path problem (APSP) can be solved in time O(nm log n) and space = O(n2). 1. construct the graph G+ by adding the vertex z and all edges from z; 2. use Bellman-Ford to compute dist+(z, v) in G+ for all vertices v, and let h(v) = dist+(z, v); 3. construct the graph G by reweighting edges [u, v] in G+: wt (u, v)=wt+(u, v)+h(u) h(v); 4. use Dijkstra to solve the APSP problem for G ; 5. Get the APSP solution to G. Can be O(n2 log n + nm), if Dijkstra uses a Fibonacci heap instead of a regular heap, with which Dijkstra will run in time O(n log n + m). Time = O(nm log n), space = O(n2)
Minimum Spanning Tree Definition. Let G be a weighted graph. A spanning tree of G is a subgraph of G that is a tree and contains all vertices of G. The weight of a spanning tree T is the sum of weights of edges in T.
Minimum Spanning Tree Definition. Let G be a weighted graph. A spanning tree of G is a subgraph of G that is a tree and contains all vertices of G. The weight of a spanning tree T is the sum of weights of edges in T. MST Problem. Given a weighted and undirected graph G, construct a minimum spanning tree of G, i.e., a spanning tree of G whose weight is the smallest over all spanning trees of G.
Minimum Spanning Tree Definition. Let G be a weighted graph. A spanning tree of G is a subgraph of G that is a tree and contains all vertices of G. The weight of a spanning tree T is the sum of weights of edges in T. MST Problem. Given a weighted and undirected graph G, construct a minimum spanning tree of G, i.e., a spanning tree of G whose weight is the smallest over all spanning trees of G. Dijkstra s approach. Idea: starting from a(ny) vertex s, grow a tree using the lightest edges.
Minimum Spanning Tree Definition. Let G be a weighted graph. A spanning tree of G is a subgraph of G that is a tree and contains all vertices of G. The weight of a spanning tree T is the sum of weights of edges in T. Dijkstra for Shortest-Paths MST Problem. Given a weighted and undirected graph G, construct a minimum spanning tree of G, i.e., a spanning tree of G whose weight is the smallest over all spanning trees of G. Dijkstra(G, s, t) 1. for (v=1; v n; v++) status[v] = unseen; 2. status[s] = in-tree; dist[s] = 0; 3. for (each edge [s, w]) status[w] = fringe; dad[w] = s; dist[w] = wt(s, w); 4. While (there are fringes) 4.1 pick the fringe v of minimum dist[v]; 4.2 status[v] = in-tree; 4.3 for (each edge [v, w]) 4.3.1 if (status[w] == unseen) status[w] = fringe; dad[w] = v; dist[w] = dist[v] + wt(v, w); 4.3.2 else if (status[w] == fringe) & (dist[w] > dist[v] + wt(v, w)) dad[w] = v; dist[w] = dist[v] + wt(v, w); 5. The array dad[1..n] gives the paths from s. Dijkstra s approach. Idea: starting from a(ny) vertex s, grow a tree using the lightest edges.
Minimum Spanning Tree Definition. Let G be a weighted graph. A spanning tree of G is a subgraph of G that is a tree and contains all vertices of G. The weight of a spanning tree T is the sum of weights of edges in T. Dijkstra for MST MST Problem. Given a weighted and undirected graph G, construct a minimum spanning tree of G, i.e., a spanning tree of G whose weight is the smallest over all spanning trees of G. Prim(G) 1. for (v=1; v n; v++) status[v] = unseen; 2. pick any vertex s; status[s] = in-tree; 3. for (each edge [s, w]) status[w] = fringe; dad[w] = s; WEIGHT[w] = wt(s, w); 4. While (there are fringes) 4.1 pick the fringe v of minimum WEIGHT[v]; 4.2 status[v] = in-tree; 4.3 for (each edge [v, w]) 4.3.1 if (status[w] == unseen) status[w] = fringe; dad[w] = v; WEIGHT[w] = wt(v, w); 4.3.2 else if (status[w] == fringe) & (WEIGHT[w] > wt(v, w)) dad[w] = v; WEIGHT[w] = wt(v, w); 5. The array dad[1..n] gives the MST rooted at s. Dijkstra s approach. Idea: starting from a(ny) vertex s, grow a tree using the lightest edges.
Minimum Spanning Tree Definition. Let G be a weighted graph. A spanning tree of G is a subgraph of G that is a tree and contains all vertices of G. The weight of a spanning tree T is the sum of weights of edges in T. Dijkstra for MST Dijkstra for Shortest-Paths Dijkstra(G, s, t) 1. for (v=1; v n; v++) status[v] = unseen; 2. status[s] = in-tree; dist[s] = 0; 3. for (each edge [s, w]) status[w] = fringe; dad[w] = s; dist[w] = wt(s, w); 4. While (there are fringes) 4.1 pick the fringe v of minimum dist[v]; 4.2 status[v] = in-tree; 4.3 for (each edge [v, w]) 4.3.1 if (status[w] == unseen) status[w] = fringe; dad[w] = v; dist[w] = dist[v] + wt(v, w); 4.3.2 else if (status[w] == fringe) & Prim(G) 1. for (v=1; v n; v++) status[v] = unseen; 2. pick any vertex s; status[s] = in-tree; 3. for (each edge [s, w]) status[w] = fringe; dad[w] = s; WEIGHT[w] = wt(s, w); 4. While (there are fringes) 4.1 pick the fringe v of minimum WEIGHT[v]; 4.2 status[v] = in-tree; 4.3 for (each edge [v, w]) 4.3.1 if (status[w] == unseen) status[w] = fringe; dad[w] = v; WEIGHT[w] = wt(v, w); 4.3.2 else if (status[w] == fringe) & (WEIGHT[w] > wt(v, w)) dad[w] = v; WEIGHT[w] = wt(v, w); 5. The array dad[1..n] gives the MST rooted at s. Dijkstra s approach. (dist[w] > dist[v] + wt(v, w)) dad[w] = v; dist[w] = dist[v] + wt(v, w); 5. The array dad[1..n] gives the paths from s.
Minimum Spanning Tree Definition. Let G be a weighted graph. A spanning tree of G is a subgraph of G that is a tree and contains all vertices of G. The weight of a spanning tree T is the sum of weights of edges in T. Dijkstra for MST MST Problem. Given a weighted and undirected graph G, construct a minimum spanning tree of G, i.e., a spanning tree of G whose weight is the smallest over all spanning trees of G. Prim(G) 1. for (v=1; v n; v++) status[v] = unseen; 2. pick any vertex s; status[s] = in-tree; 3. for (each edge [s, w]) status[w] = fringe; dad[w] = s; WEIGHT[w] = wt(s, w); 4. While (there are fringes) 4.1 pick the fringe v of minimum WEIGHT[v]; 4.2 status[v] = in-tree; 4.3 for (each edge [v, w]) 4.3.1 if (status[w] == unseen) status[w] = fringe; dad[w] = v; WEIGHT[w] = wt(v, w); 4.3.2 else if (status[w] == fringe) & (WEIGHT[w] > wt(v, w)) dad[w] = v; WEIGHT[w] = wt(v, w); 5. The array dad[1..n] gives the MST rooted at s. Theorem. The Minimum Spanning Tree Problem can be solved in time O(m log n) or O(n2).
