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 ✕

Coding Tools

Online Python IDE LMC Simulator Flowchart Sudio Trace Table 101 Dashboard

Design Tools

Network Designer Database ERD Designer

Logic Gates Circuits

Logic Gates Circuits Simulator Logic Gates Diagrams Binary Activities Karnaugh Maps

Cryptography Corner

Enigma Simulator Enigma Mission X Turing-Welchman Bombe Simulator Frequency Analysis Cipher Wheel Visual Cryptography Pigpen Cipher Encoder MRX20 Mission to Mars Cryptography Challenges

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...