LAB MANUAL DATA STRUCTURES
LAB NO. 15 25/11/2025
Shortest-Path Graphs
1. Lab outcomes:
After completing this lab, students will be able to:
Explain the concept of shortest-path in graphs.
Demonstrate the applications of Djikstras and Bellman Ford algorithms.
Implement the shortest-path algorithms in graphs.
2. Outline:
Weighted Graphs
Djikstra
Bellman Ford
Shortest-Path
3. Theory:
In today’s lab, you will explore Shortest Path Graphs, a type of graph where edges
have weights that represent costs, distances, or times between nodes. Finding the
shortest path is a fundamental problem in computer science, networking, and AI,
where efficient routes or minimal-cost paths are critical.
Key aspects of Shortest Path Graphs:
Weighted Graphs: Each edge has a numerical weight, such as distance between
cities, time to traverse a network link, or cost of travel.
Directed vs. Undirected: Weights may apply to one-way connections (directed)
or two-way links (undirected).
Negative Weights: Some algorithms, like Bellman-Ford, can handle edges with
negative weights, while Dijkstra cannot.
Pathfinding: Shortest path algorithms calculate the minimal total weight between
a source node and other nodes in the graph.
1
NATIONAL UNIVERSITY OF COMPUTER AND EMERGING
SCIENCES
LAB MANUAL DATA STRUCTURES
Applications in AI and Data Science:
Navigation Systems: Finding the fastest route in maps or transportation networks.
Network Optimization: Minimizing costs in communication or logistics
networks.
Game AI: Determining efficient paths for characters or agents in virtual
environments.
4. Lab Tasks:
Please make sure that you submit the files with the following naming convention:
24x-xxxx_taskx_main.cpp. Not following the convention could result in zero.
Lab Task 1: Implementing Dijkstra’s Algorithm on Mini Islamabad Graph
Objective:
Understand and implement a graph data structure using adjacency lists, and apply
Dijkstra’s algorithm to find the shortest path between two nodes.
Starter Code:
You are provided with a C++ starter code that contains:
Classes for Node and Edge.
A Graph class with adjacency lists.
Functions for loading graph data from a CSV file and printing results.
Your Tasks:
Implement getNodeIndex() function
Search for a node by its name in the nodes array.
If the node exists, return its index.
If it does not exist, add a new node to the array and return its index.
Handle the case where the number of nodes exceeds MAX_NODES.
Implement addEdge() function
Create a new Edge from from to to with the given weight.
Add this edge to the adjacency list of the from node.
Implement minDistance() function
Search for the next neighbor with the minium cost.
After implementing it with the brute force appraoch, optimize it using Min-
Heap. You can use your implementation of Heap from previous labs.
Implement Dijkstra’s Algorithm in dijkstra() function
2
NATIONAL UNIVERSITY OF COMPUTER AND EMERGING
SCIENCES
LAB MANUAL DATA STRUCTURES
Initialize distance and visited arrays.
Use the minDistance() helper to find the next closest unvisited node.
Update distances for all adjacent nodes.
Track the parent of each node to reconstruct the shortest path.
Output
Print the shortest distance from a source to a target node.
Print the path from the source to the target node in order.
Example Output:
3
NATIONAL UNIVERSITY OF COMPUTER AND EMERGING
SCIENCES