Graphs

Graphs! We keep them in memory either as an adjacency list or an adjacency matrix. The implication here is that we care about the things that are adjacent, or connected, in the graph.

Breaking down from there, we have a few major categories:

• Directed
• Nondirected
• Weighted

Shortest path algorithms:

Dijkstra's Algorithm

1. Pick the node from which you want to find shortest paths
2. Add all vertexes to a min-priority queue with a weight of infinity
3. For each edge, compute the weight to the next vertex. Update the weight in the min priority queue.
4. When you're done, pick the min in the min-priority queue and remove it. That's your new base
5. From that base, examine all the edges around it. If the weight of the vertex you're on + the edge weight is smaller than the existing weight, update the weight in the min priority queue.
6. You're done with this vertex! go to the next one in the min-priority queue.

When do I use Dijkstra's?

• When there's no chance of a negative cycle (no negative weights)

Bellman-Ford

1. Pick your starting point! It's weight is set to 0, all others are set to infinity
2. We're going to iterate v-1 times, and for each we will scan every edge. If the distance from the initial node can be shortened by following the edge, relax the weight of the vertex.
3. Repeat this v-1 times, relaxing the edges on each go. Since we'll have different starting weights each time, this will give us different relaxations for a while.
4. Basically, we're letting the relaxations propogate by looking at it over and over again. Runtime is |v|*|e|
5. At the end, scan again. If you can find a lower weight, there's a negative cycle

When do I use Bellman-fords?'s?

• Directed, weighted graphs!