djikstras shortest path algorithm Flashcards
(23 cards)
What are the properties of graphs?
Graph properties can be:
* Connected
* Weighted
* Non-negative
* Directed
Directed graphs can have edges that go in one direction only.
What does the variable ‘n’ represent in graph theory?
Number of Nodes
‘n’ denotes the total count of vertices in the graph.
What does the variable ‘m’ represent in graph theory?
Number of edges
‘m’ denotes the total count of edges connecting the nodes.
Define a path in graph theory.
Edge of one vertex connects to the next, can be followed from a source to a destination.
What is the shortest path?
Minimum total sum of edge weights.
What are the types of path problems?
Types of path problems include:
* Single-pair shortest path
* Single-source shortest path
* All-pairs shortest path
Each type addresses different shortest path queries in a graph.
What is the single-pair shortest path problem?
Find shortest path between specific vertices v and u.
What is the single-source shortest path problem?
Shortest path from specific vertex v to all other nodes.
What is the all-pairs shortest path problem?
Shortest paths between all pairs of nodes.
What formula gives the total amount of edges in a graph?
(n-1)^2
This formula estimates the maximum number of edges in a complete graph.
What is true about any prefix of the shortest path?
Any prefix of the shortest path from v is also a shortest path from v.
What is the main concept of Dijkstra’s algorithm?
Incrementally adding nodes that we know are the shortest path.
How does Dijkstra’s algorithm expand the set of nodes?
Find node that can be reached by a single edge from the current set, with the minimum total weight over the whole shortest path.
What do Dist(u) and Pre(u) represent in Dijkstra’s algorithm?
Dist(u) = distance of shortest v -> u path found so far; Pre(u) = predecessor of u on the shortest path v -> u path so far.
In Dijkstra’s algorithm, what is the initial distance for the source node?
dist(v) = 0.
What is the initial distance for all other nodes in Dijkstra’s algorithm?
dist(u) = infinity for all u != v.
What is the total complexity of Dijkstra’s algorithm using simple data structures?
O(n^2).
What is the total complexity of Dijkstra’s algorithm when using binary heaps or BST?
O(m log n).
What is an important condition for Dijkstra’s algorithm to work correctly?
Edge weights must be non-negative.
What should be used if negative edge weights are present?
Slower algorithms must be used.
What is the total average time complexity?
Big O
O(n^2)
What is the total average time complexity of djikstras with a heap/bst?
O( m log n)
m is number of edges, n is number of nodes
