B.M.S.

COLLEGE OF ENGINEERING
(Autonomous college under VTU)
Bull Temple Rd, Basavanagudi, Bengaluru, Karnataka
2023-2024
Department of Computer Applications
Report is submitted for fulfillment of AAT work in the subject

“DATA STRUCTURES AND ALGORITHMS”

(22MCA2PCDS)
(Batch 2023)

By

BHASKAR S(1BM23MC021)

HRUTHIK CHAVAN D(1BM23MC022)

MANOHAR T H(1BM23MC051)

MUNESH SAGAR K (1BM23MC055)

Under the Guidance

T S Pushpa
(Assistant Professor)
 CONTENTS

SL. Page
No. Programs No.

1. Problem Statement

Design Technique &/Data Structures used

2.

Source Code
3.

Results (Screen shots)

4.

Time /Space Complexity

5.

Comparison of time/space complexity when implemented in more than one

6.
programming language/implanted using different design techniques

Conclusion
7.

Team Contribution Details

8.

Reference
9.
22MCA2PCDS: Data Structures and Algorithms

1. Problem Statement
Implement the Best First Search algorithm to find the shortest path between a
given start node and a goal node in a graph. The algorithm should account for
different possible paths, select the most efficient one based on a cost function, and
ensure optimal performance in terms of both time and space.

Design an BEST FIRST SEARCH algorithm to find the shortest path between two
nodes in a weighted, undirected graph. The algorithm should account for both the
cost to reach a node (g_score) and an estimated cost to reach the goal (heuristic
h_score). Visualize the graph, highlight the shortest paths, and provide details
about total path costs.

The graph can represent any real-world scenario, such as navigating through a
map, where nodes represent points of interest, and edges represent the paths
between them with respective weights.

2. Design Technique &/Data Structures used

Design Technique

The Best First Search algorithm uses a Greedy Best-First Search combined with
Dijkstra's algorithm principles. It incorporates both the actual distance from the
start node (g_score) and a heuristic estimate (h_score) of the distance to the goal.
A* prioritizes nodes based on their total estimated cost (f_score = g_score +
h_score).

Key Steps:
1. Maintain an open set of nodes to be evaluated.
2. Track g_score for each node (cost to reach the node).
3. Use a priority heuristic (f_score = g_score + heuristic) to select nodes.
4. For each node, compute tentative scores and update paths.
5. Continue until the goal node is reached or the open set is empty.

Department of Computer Applications, BMSCE 1

22MCA2PCDS: Data Structures and Algorithms

Data Structures Used:

1. Graph Representation: The graph is stored as a weighted undirected graph
using the NetworkX library. Nodes are connected by edges with associated
weights.
2. Heuristic: A dictionary stores heuristic estimates of distances from nodes to
the goal.
3. Open Set: A set containing nodes to be evaluated. This set could be enhanced
using a priority queue for better performance.
4. g_score and f_score: Dictionaries track the cost to reach nodes and the total
cost estimates, respectively.
5. Came_from Map: A dictionary to reconstruct the shortest path by
backtracking from the goal to the start.

Department of Computer Applications, BMSCE 2

22MCA2PCDS: Data Structures and Algorithms

3. Source Code
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>

#define MAX_NODES 10
#define INFINITY INT_MAX

typedef struct {
char name; // Node name for output
int edges[MAX_NODES]; // Adjacency list
int edgeCount; // Number of edges
int cost[MAX_NODES]; // Costs for each edge
} Node;

Node graph[MAX_NODES];
bool openList[MAX_NODES];
bool closedList[MAX_NODES];
int gCost[MAX_NODES]; // Cost from start to node
int parent[MAX_NODES]; // Parent node for path reconstruction
int nodeCount = 0;

// Add a node to the graph

void addNode(char name) {
graph[nodeCount].name = name;
graph[nodeCount].edgeCount = 0;
gCost[nodeCount] = INFINITY;
parent[nodeCount] = -1;
nodeCount++;
}

// Add an edge between two nodes

void addEdge(int from, int to, int cost) {
graph[from].edges[graph[from].edgeCount] = to;
graph[from].cost[graph[from].edgeCount] = cost;
graph[from].edgeCount++;
}

// A* algorithm to find the shortest path

void aStar(int startIdx, int goalIdx) {
Department of Computer Applications, BMSCE 3
22MCA2PCDS: Data Structures and Algorithms

gCost[startIdx] = 0;
openList[startIdx] = true;

while (true) {
int minIndex = -1;
for (int i = 0; i < nodeCount; i++) {
if (openList[i] && (minIndex == -1 || gCost[i] < gCost[minIndex])) {
minIndex = i;
}
}

if (minIndex == -1) {
printf("No path found\n");
return;
}

if (minIndex == goalIdx) {
printf("Path found: ");
int current = goalIdx;
while (current != -1) {
printf("%c", graph[current].name);
if (parent[current] != -1) printf7("->");
current = parent[current];
}
printf(" = [%d]\n", gCost[goalIdx]);
return;
}

openList[minIndex] = false;

for (int i = 0; i < graph[minIndex].edgeCount; i++) {

int adjIdx = graph[minIndex].edges[i];
int cost = gCost[minIndex] + graph[minIndex].cost[i];

if (cost < gCost[adjIdx]) {

gCost[adjIdx] = cost;
parent[adjIdx] = minIndex;
openList[adjIdx] = true;
}
}
}
Department of Computer Applications, BMSCE 4
22MCA2PCDS: Data Structures and Algorithms

int main() {
// Setup graph
addNode('A'); // Node 0
addNode('B'); // Node 1
addNode('C'); // Node 2
addNode('D'); // Node 3
addNode('E'); // Node 4

// Add edges (with costs)

addEdge(0, 1, 1); // A -> B
addEdge(0, 2, 4); // A -> C
addEdge(1, 2, 2); // B -> C
addEdge(1, 3, 5); // B -> D
addEdge(2, 4, 3); // C -> E
addEdge(3, 4, 1); // D -> E

int startIdx = 0; // Start node (A)

int goalIdx = 4; // Goal node (E)

aStar(startIdx, goalIdx);

return 0;
}
OUTPUT:

Department of Computer Applications, BMSCE 5

22MCA2PCDS: Data Structures and Algorithms

IN Python:
import heapq

class Graph:
def _init_(self):
self.edges = {}
self.h_weights = {}

def add_edge(self, node1, node2, cost):

if node1 not in self.edges:
self.edges[node1] = []
if node2 not in self.edges:
self.edges[node2] = []
self.edges[node1].append((node2, cost))
self.edges[node2].append((node1, cost))

def set_heuristic(self, node, heuristic):

self.h_weights[node] = heuristic

def heuristic(self, node, target):

return self.h_weights.get(node, 0)

def a_star(self, start, goal):

open_set = []
heapq.heappush(open_set, (0, start))
came_from = {start: None}
g_score = {start: 0}

while open_set:
_, current = heapq.heappop(open_set)

if current == goal:
return self.reconstruct_path(came_from, current, g_score)

for neighbor, cost in self.edges.get(current, []):

tentative_g_score = g_score[current] + cost
if tentative_g_score < g_score.get(neighbor, float('inf')):
came_from[neighbor] = current
g_score[neighbor] = tentative_g_score
f_score = tentative_g_score + self.heuristic(neighbor, goal)
heapq.heappush(open_set, (f_score, neighbor))

Department of Computer Applications, BMSCE 6

22MCA2PCDS: Data Structures and Algorithms

return None, float('inf')

def reconstruct_path(self, came_from, current, g_score):

total_path = [current]
while current in came_from and came_from[current] is not None:
current = came_from[current]
total_path.append(current)
total_path.reverse()
return total_path, g_score[total_path[-1]]

def a_star_all_nodes(self, start):

paths = {}
for node in self.edges:
if node != start:
path, cost = self.a_star(start, node)
if path:
paths[node] = (path, cost)
else:
paths[node] = "No path"
return paths

def format_path(self, path, cost):

if isinstance(path, str):
return path
return " -> ".join(path) + f" = [{cost}]"

# Example Usage
graph = Graph()

# Add edges (node1, node2, cost)

graph.add_edge('A', 'B', 1)
graph.add_edge('A', 'C', 3)
graph.add_edge('B', 'D', 1)
graph.add_edge('B', 'E', 5)
graph.add_edge('C', 'F', 2)
graph.add_edge('D', 'E', 1)
graph.add_edge('E', 'F', 2)

# Set heuristic values (node, heuristic-to-goal)

graph.set_heuristic('A', 6)
graph.set_heuristic('B', 4)
Department of Computer Applications, BMSCE 7
22MCA2PCDS: Data Structures and Algorithms

graph.set_heuristic('C', 3)
graph.set_heuristic('D', 2)
graph.set_heuristic('E', 1)
graph.set_heuristic('F', 0)

# Find shortest path between 'A' and 'F'

shortest_path, cost = graph.a_star('A', 'F')
print(f"Shortest path from A to F: {graph.format_path(shortest_path, cost)}")

# Find shortest paths from 'A' to all other nodes

all_paths = graph.a_star_all_nodes('A')
print("Shortest paths from A to all other nodes:")
for node, (path, cost) in all_paths.items():
print(f"To{node}:{graph.format_path(path,cost)}")

Department of Computer Applications, BMSCE 8

22MCA2PCDS: Data Structures and Algorithms

In java
import java.util.*;

class Node implements Comparable<Node> {

String name;
Map<Node, Integer> edges;
int g; // Cost from start to this node
int h; // Heuristic estimate of cost from this node to goal
Node parent;

Node(String name) {
this.name = name;
edges = new HashMap<>();
}

void addEdge(Node neighbor, int weight) {

edges.put(neighbor, weight);
}

@Override
public int compareTo(Node other) {
return Integer.compare(g + h, other.g + other.h);
}
}

class Graph {
Map<String, Node> nodes;

Graph() {
nodes = new HashMap<>();
}

Node getNode(String name) {

if (!nodes.containsKey(name)) {
nodes.put(name, new Node(name));
}
return nodes.get(name);
}

void addEdge(String from, String to, int weight) {

Node fromNode = getNode(from);
Department of Computer Applications, BMSCE 9
22MCA2PCDS: Data Structures and Algorithms

Node toNode = getNode(to);

fromNode.addEdge(toNode, weight);
toNode.addEdge(fromNode, weight); // For undirected graph
}
}

class AStar {
static List<String> findShortestPath(Node start, Node goal) {
PriorityQueue<Node> open = new PriorityQueue<>();
Set<Node> closed = new HashSet<>();
start.g = 0;
start.h = heuristic(start, goal);
open.offer(start);

while (!open.isEmpty()) {
Node current = open.poll();
if (current == goal) {
return reconstructPath(current);
}
closed.add(current);
for (Map.Entry<Node, Integer> entry : current.edges.entrySet()) {
Node neighbor = entry.getKey();
int tentativeG = current.g + entry.getValue();
if (closed.contains(neighbor) && tentativeG >= neighbor.g) {
continue;
}
if (!open.contains(neighbor) || tentativeG < neighbor.g) {
neighbor.parent = current;
neighbor.g = tentativeG;
neighbor.h = heuristic(neighbor, goal);
if (!open.contains(neighbor)) {
open.offer(neighbor);
}
}
}
}
return null; // No path found
}

static List<String> reconstructPath(Node node) {

List<String> path = new ArrayList<>();
Department of Computer Applications, BMSCE 10
22MCA2PCDS: Data Structures and Algorithms

while (node != null) {

path.add(0, node.name); // Add to the front of the list
node = node.parent;
}
return path;
}

static int heuristic(Node a, Node b) {

// Heuristic function (e.g., straight-line distance)
return 0; // Replace with actual heuristic if needed
}

static Map<String, String> findShortestPathsFromSource(Graph graph, String

source) {
Map<String, String> pathsFromSource = new HashMap<>();
Node sourceNode = graph.getNode(source);

for (Node goalNode : graph.nodes.values()) {

if (!goalNode.equals(sourceNode)) {
List<String> path = findShortestPath(sourceNode, goalNode);
if (path != null) { // Check if a path exists
int cost = calculatePathCost(path, graph);
pathsFromSource.put(goalNode.name, String.join(" -> ", path) + " = [" +
cost + "]");
} else {
pathsFromSource.put(goalNode.name, "No path");
}
}
}

return pathsFromSource;
}

static int calculatePathCost(List<String> path, Graph graph) {

int cost = 0;
for (int i = 0; i < path.size() - 1; i++) {
Node currentNode = graph.getNode(path.get(i));
Node nextNode = graph.getNode(path.get(i + 1));
cost += currentNode.edges.get(nextNode); // Get the edge weight
}
return cost;
Department of Computer Applications, BMSCE 11
22MCA2PCDS: Data Structures and Algorithms

}
}

public class Main {

public static void main(String[] args) {
Graph graph = new Graph();

// Define nodes
String[] nodes = {"A", "B", "C", "D", "E", "F"};

// Add nodes to the graph

for (String node : nodes) {
graph.getNode(node);
}

// Define edges with weights

graph.addEdge("A", "B", 1);
graph.addEdge("A", "C", 3);
graph.addEdge("B", "D", 1);
graph.addEdge("C", "D", 1);
graph.addEdge("D", "E", 1);
graph.addEdge("E", "F", 2);

// Set the source node

String sourceNode = "A";
String destinationNode = "F";

// Find the shortest path from source to destination (A -> F)

List<String> specificPath = AStar.findShortestPath(graph.getNode(sourceNode),
graph.getNode(destinationNode));
if (specificPath != null) {
int cost = AStar.calculatePathCost(specificPath, graph);
System.out.println("Shortest path from " + sourceNode + " to " +
destinationNode + ": " + String.join(" -> ", specificPath) + " = [" + cost + "]");
} else {
System.out.println("No path from " + sourceNode + " to " + destinationNode);
}

// Find and print all shortest paths from the source node to all other nodes
System.out.println("\nShortest paths from " + sourceNode + " to all other
nodes:");
Map<String, String> shortestPathsFromSource =
Department of Computer Applications, BMSCE 12
22MCA2PCDS: Data Structures and Algorithms

AStar.findShortestPathsFromSource(graph, sourceNode);
for (Map.Entry<String, String> entry : shortestPathsFromSource.entrySet()) {
System.out.println("To " + entry.getKey() + ": " + entry.getValue());
}
}
}

OUTPUT:

Department of Computer Applications, BMSCE 13

22MCA2PCDS: Data Structures and Algorithms

4. Time /Space Complexity

Time and Space Complexity:

 Time Complexity: O(E + V log V), where:

o V is the number of vertices.
o E is the number of edges. This assumes efficient data structures
like a min-heap priority queue for the open set, which reduces
the cost of finding the minimum f_score.

 Space Complexity: O(V), where:

o V is the number of vertices (for storing g_score, f_score, and
came_from dictionaries).

5. Comparison of time/space complexity when implemented in

more than one programming language/implanted using
different design techniques

Python Implementation:
 Time Complexity: O(E + V log V)
 Space Complexity: O(V)

C Implementation
 Time Complexity: O(E + V log V)
 Space Complexity: O(V)

Java Implementation:
 Time Complexity: O(E + V log V)
 Space Complexity: O(V)

Department of Computer Applications, BMSCE 14

22MCA2PCDS: Data Structures and Algorithms

6. Conclusion
The A* algorithm's performance varies significantly depending on the
programming language and the efficiency of the underlying data structures used.
In general:
 Python is user-friendly and suitable for rapid prototyping but may face
performance bottlenecks due to its higher-level abstractions and memory
management. Utilizing a priority queue (like heapq) can improve time
complexity, but Python's inherent overhead still makes it slower compared to
lower-level languages.

 Java provides a balance between performance and ease of use, with better
execution speed than Python and the benefit of a rich standard library.
However, it still incurs some overhead from the JVM, making it slower than
C++.

 C delivers the most optimized solution for both time and space, as developers
have direct control over memory allocation and data structures. It is the go-to
choice for highly performance-sensitive applications where minimal overhead
is essential.

7. Reference

 Russell, S. J., & Norvig, P. (2009). Artificial Intelligence: A Modern Approach

(3rd ed.). Prentice Hall.
 Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A Formal Basis for the
Heuristic Determination of Minimum Cost Paths. IEEE Transactions on
Systems Science and Cybernetics.
 NetworkX Documentation: https://networkx.github.io/

Department of Computer Applications, BMSCE 15