Graph

• a graph consists of the following
  1. A set of elements called nodes (or vertices)
  2. A set of connections between pairs of nodes called edges

• a graph can be in the form:

  1. An unstructured set, such as a disconnected group of nodes
  2. A sequential set - where order matters - of connected nodes and edges
  3. A hierarchical set - where rank exists (i.e. "parents", "successors", etc) - of connected nodes and edges
  4. A structured set of both connected and disconnected nodes and edges

• represent a graph: G = (V, E), where V is the set of vertices in G and E is the set of edges in G.

• One way to represent a graph is by using an adjacency matrix. space complexity (i.e., the amount of space that this matrix takes up) is O(|V|²).

• represent sparse graphs: the adjacency list. our space complexity becomes O(|V|+|E|).

• Dijkstra's Algorithm: The idea behind Dijkstra's Algorithm is that we are constantly looking for the lowest-weight paths and seeing which vertices are discovered along the way

  1. Algorithm: walk along the shortest path from start node, and record the nodes that we encounter along the path.
  2. It takes advantage of the Priority Queue ADT to store the possible paths and uses the total weights of the paths to determine priority.
  3. The vertices should have 3 fields a. Distance: the shortest path that was discovered to get to this vertex b. Previous: the vertex right before it, so we can keep track of the path and overall structure of the graph c. Done: a Boolean field to determine if a shortest path has already been found to this vertex
  4. Dijkstra's Algorithm guarantees that, for each vertex, the first time an instance of it is removed from the priority queue, a shortest path to it has been found.
  5. Assumption: no negative weight edges can exist in the graph

REFERENCE: Stepik 4.1-4.5