101Computing.net

Learning Zone ✕

Theory Concepts

Cryptography Computer Hardware Computer Networks Algorithms OOP Programming Binary Data Boolean Logic Database Concepts

Interactive Quizzes

View All Quizzes

GCSE Computer Science (UK)

1.1 System Architecture 1.2 Memory and Storage 1.3 Computer networks 1.4 Network security 1.5 – Systems software 1.6 – Impacts of digital technology

2.1 – Algorithms 2.2 – Programming fundamentals 2.3 – Producing robust programs 2.4 – Boolean logic 2.5 – Programming languages and IDEs

A-Level Computer Science (UK)

1.1 Contemporary processors, input, output and storage devices 1.2 Software and software development 1.3 Exchanging data 1.4 Data types, data structures and algorithms 1.5 Legal, moral, cultural and ethical issues

2.1 Elements of computational thinking 2.2 Problem solving and programming 2.3 Algorithms

Coding Challenges ✕

Python Challenges

Python Challenges - All Levels Python Challenges - Beginner Level Python Challenges - Intermediate Level Python Challenges - Advanced Level Python Turtle Challenges Solved Challenges

HTML / CSS & JavaScript

HTML / CSS & JavaScript

LMC

LMC Challenges LMC Simulator

SQL

SQL Challenges

Block Programming

BBC micro:bit Challenges Scratch Challenges

Interactive Coding Puzzles

Pirate Island Space Explorer Interactive Coding Quizzes

Online Interactive Tools ✕

More results...

◑ Python IDE Dashboard

Member's Area ✕

Register/Sign Up

Become a Member Login Your Account Solved Challenges Membership FAQ Logout

Get In Touch

About Us Contact Us Follow Us

Books Corner

101 Python Challenges 101 Extra Python Challenges

Sign Up Log In

Short Path Algorithm Practice

Posted on January 10, 2023 by Administrator Posted in A Level Concepts, A Level Quiz, Algorithms, Computer Science, Computing Concepts

Before completing this task, you will need to familiarise yourself with the following 2 algorithms used to find the shortest path between two nodes of a weighted graph:

Dijkstra’s Short Path Algorithm

For each of the weighted graph below, complete the table below to show the steps needed to find the shortest path between node A and node Z using the Dijkstra’s Short Path Algorithm. Note that on these graphs, the weight of each edge represents the distance in miles between two nodes.

Graph #1Graph #2Graph #3Graph #4

Shortest Path?

Length?

Shortest Path?

Length?

Shortest Path?

Length?

Shortest Path?

Length?

Node	Status	Shortest Distance from A	Previous Node
A
B
C
D
E
F
G
H
Z

A* Algorithm

On the graphs below, the heuristic values specified for each node of the graph represent the distance in a straight line (as the crow flies) between the node and the destination node (Z).

Graph #1Graph #2Graph #3Graph #4

Shortest Path?

Length?

Shortest Path?

Length?

Shortest Path?

Length?

Shortest Path?

Length?

Node	Status	Shortest Distance from A	Heurisitic Distance to Z	Total Distance	Previous Node
A
B
C
D
E
F
G
H
Z

Other challenges you may enjoy...