Dijkstra's Shortest Path Algorithm (OCR A-Level Computer Science): Flashcards

📚Flashcards
Revision NotesModel AnswersQuizzesFlashcardsExam Questions
Dijkstra's Shortest Path Algorithm
Sign up to keep revising.Create a free account to study more flashcards and track your progress.

Practise the cards

12 cards from this deck

Show

Purpose of Dijkstra's Algorithm

Find shortest path from source node to all other nodes

Edge weight requirement for Dijkstra's

Non-negative edge weights

Initial distance: source node in Dijkstra's

0

Initial distance: other nodes in Dijkstra's

Infinity (∞\infty)

Algorithm type: Dijkstra's

Greedy algorithm

Time complexity: Dijkstra's (adjacency matrix)

O(V2)O(V^2)

Time complexity: Dijkstra's (priority queue)

O((V+E)log⁡V)O((V + E) \log V)

Space complexity: Dijkstra's Algorithm

O(V+E)O(V + E)

Are visited nodes revisited in Dijkstra's?

No

When is a node marked visited in Dijkstra's?

After all neighbours are evaluated

Data structure for efficient Dijkstra's implementation

Priority queue

Node selection criterion in Dijkstra's

Unvisited node with smallest known distance

Explore OCR A-Level Computer Science Revision Notes by Topics

Algorithms

Algorithms for the Main Data Structures

Explore OCR A-Level Computer Science Model Answers by Topics

Algorithms

Algorithms for the Main Data Structures

Explore OCR A-Level Computer Science Quizzes by Topics

Algorithms

Algorithms for the Main Data Structures

Explore OCR A-Level Computer Science Exam Questions by Topics

Algorithms

Algorithms for the Main Data Structures

Join 100,000+ A-Level students studying Flashcards with us.

Select your subjects, and get access to A+ resources today.