# DSA

- StudyBlue
- United Kingdom
- University of Bristol
- Mathematics And Computer Science
- Mathematics And Computer Science 101
- Lecturers
- DSA

**Created:**2016-12-30

**Last Modified:**2016-12-30

- Computes the minimum distance from a source node 's' to every other node in the graph
- Directed or undirected
- Uses a
**QUEUE**structure - Runtime: O(V + E)

- Computes the minimum distance from a source node 's' to every other node in the graph
- Directed or undirected
- Uses a
**STACK**structure - Runtime: O(V + E)

*uv*from vertex

*u*to vertex

*v*,

*u*comes before

*v*in the ordering.

- Characterise the structure of an
**optimal solution** **Recursively**define the value of an optimal solution- compute the value of an optimal solution in a
**bottom-up**fashion - construct an optimal solution from constructed information

- Finds a minimum spanning tree or forest of a connected or disconnected graph
- Order the edges by increasing weight, go through this list, adding an edge if it does not create a cycle.
- runtime O(Elog(V))

- Finds a minimum spanning tree of a connected, undirected graph
- Grow the tree by one edge at a time, pick the minimum edge connecting the tree to the vertices not in the tree
- runtime: O(V
^{2})

- Finds the shortest path from a source node 's' to every other node in the graph
- Weighted, directed, negative edges ok
- AT MOST will iterate |V| - 1 times
- source vertex given path weight 0, all other vertices have path weight infinity. go through the vertices, looking at outward edges to find shorter paths to other evrtices.

- Finds the shortest path between
**all**pairs of vertices - weighted, directed graph, negative edges ok
- if (dist[i][j] > dist [i][k] + dist [k][j])
- O(|V|
^{3})

- Finds the shortest path from a source node 's' to every other node
- weighted, directed graph, negative edges not ok
- Set source, find path weights to neightbours, pick node with smallest weight, repeat
- runtime: O(|E| + |V|log|V|

- runtime: O(n log n)

#### Words From Our Students

"StudyBlue is great for studying. I love the study guides, flashcards, and quizzes. So extremely helpful for all of my classes!"

Alice, Arizona State University

"I'm a student using StudyBlue, and I can 100% say that it helps me so much. Study materials for almost every subject in school are available in StudyBlue. It is so helpful for my education!"

Tim, University of Florida

"StudyBlue provides way more features than other studying apps, and thus allows me to learn very quickly! I actually feel much more comfortable taking my exams after I study with this app. It's amazing!"

Jennifer, Rutgers University

"I love flashcards but carrying around physical flashcards is cumbersome and simply outdated. StudyBlue is exactly what I was looking for!"

Justin, LSU