Data Structure

LECTURE # 13

​

What is the Shortest Path Problem?

The shortest path problem is a classic problem in graph theory and computer science. It involves finding the minimum-weight path between two nodes in a weighted graph.

Types of Shortest Path Problems

There are several types of shortest path problems:

1. Single-Source Shortest Paths (SSSP): Find the shortest path from a single source node to all other nodes in the graph.
2. Single-Destination Shortest Paths (SDSP): Find the shortest path from all nodes in the graph to a single destination node.
3. All-Pairs Shortest Paths (APSP): Find the shortest path between all pairs of nodes in the graph.

Algorithms for shortest Path;

Several algorithms can be used to solve the shortest path problem:

1. Dijkstra's Algorithm: A popular algorithm for finding the shortest path in a weighted graph. It works by maintaining a priority queue of nodes to visit, where the priority of each node is its minimum distance from the source node.
2. Bellman-Ford Algorithm: An algorithm that can handle negative weight edges, which Dijkstra's algorithm cannot.
3. Floyd-Warshall Algorithm: An algorithm for finding the shortest path between all pairs of nodes in a weighted graph.

C++ implementation of Dijkstra's algorithm for finding the shortest path in a weighted graph:

#include <iostream>

#include <vector>

#include <queue>

#include <limits>

using namespace std; // Structure to represent a graph edge

struct Edge { int destination; int weight;}; // Structure to represent a graph node

struct Node { int id; int distance; bool visited;}; // Function to implement Dijkstra's algorithm

void dijkstra(vector<vector<Edge>>& graph, int source) { int numNodes = graph.size(); vector<Node> nodes(numNodes); // Initialize nodes

for (int i = 0; i < numNodes; i++) { nodes[i].id = i;

nodes[i].distance = numeric_limits<int>::max();

nodes[i].visited = false; } // Set distance of source node to 0

nodes[source].distance = 0; // Create a priority queue to hold nodes to visit

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> queue;

queue.push({0, source});

while (!queue.empty()) { int currentNode = queue.top().second;

queue.pop();

if (nodes[currentNode].visited) { continue; }

nodes[currentNode].visited = true; // Update distances of neighboring nodes

for (const Edge& edge : graph[currentNode])

{ int neighbor = edge.destination; int weight = edge.weight;

if (nodes[neighbor].distance > nodes[currentNode].distance + weight)

{nodes[neighbor].distance = nodes[currentNode].distance + weight; queue.push({nodes[neighbor].distance, neighbor});

}

}

} // Print shortest distances

for (const Node& node : nodes) {cout << "Node " << node.id << ": " << node.distance << endl; }}int main() {

// Create a sample graph

int numNodes = 5; vector<vector<Edge>> graph(numNodes); graph[0].push_back({1, 4}); graph[0].push_back({2, 1});

graph[1].push_back({3, 1});

graph[2].push_back({1, 2});

graph[2].push_back({3, 5});

graph[3].push_back({4, 3}); // Run Dijkstra's algorithm

int source = 0;

dijkstra(graph, source);  

return 0;}

Adjacency Matrix Representation

An adjacency matrix is a square matrix used to represent a finite graph. The matrix has a size of V x V, where V is the number of vertices in the graph.

How it Works

In an adjacency matrix, the entry at row i and column j represents the weight of the edge between vertex i and vertex j. If there is no edge between the vertices, the entry is typically set to 0 or a special value indicating the absence of an edge.

Advantages

1. Fast edge lookup: Checking if an edge exists between two vertices can be done in constant time, O(1).
2. Easy to implement: The adjacency matrix representation is straightforward to implement.

Disadvantages

1. Space complexity: The adjacency matrix requires O(V^2) space, which can be inefficient for large graphs with many vertices.
2. Slow edge insertion/deletion: Inserting or deleting an edge requires updating the entire row and column of the matrix, which can be slow.

C++ Implementation of Adjacency Matrix

#include <iostream>

#include <vector>

#include <list>

class AdjacencyList {

private:

int numVertices;

std::vector<std::list<std::pair<int, int>>> adjacencyList;

public:

AdjacencyList(int numVertices) : numVertices(numVertices), adjacencyList(numVertices) {}

void addEdge(int source, int destination, int weight)

{ if (source >= 0 && source < numVertices && destination >= 0 && destination < numVertices)

{ adjacencyList[source].push_back(std::make_pair(destination, weight));

}

} void removeEdge(int source, int destination)

{ if (source >= 0 && source < numVertices && destination >= 0 && destination < numVertices) {    adjacency

Memory Management

In C++Memory management is the process of managing the memory allocated to a program. In C++, memory management is manual, meaning that the programmer is responsible for allocating and deallocating memory.

Types of Memory

in C++There are two types of memory in C++:

1. Stack Memory: Stack memory is used to store local variables, function parameters, and return addresses. Stack memory is automatically managed by the compiler.
2. Heap Memory: Heap memory is used to store dynamically allocated memory. Heap memory is manually managed by the programmer.

Memory Allocation in C++

Memory allocation in C++ can be done using the following operators:

1. new: The new operator is used to allocate memory on the heap. It returns a pointer to the allocated memory.
2. delete: The delete operator is used to deallocate memory on the heap.

Example of Memory Allocation in C++

int* ptr = new int; // Allocate memory for an integer

*ptr = 10; // Assign a value to the allocated memory

delete ptr; // Deallocate the memory

​

Memory Leaks in C++

A memory leak occurs when memory is allocated but not deallocated. Memory leaks can cause a program to consume increasing amounts of memory, leading to performance issues and crashes.

​

Example of a Memory Leak in C++

int* ptr = new int; // Allocate memory for an integer

*ptr = 10; // Assign a value to the allocated memory

// No deallocation of memory

Garbage Collection in C++

Garbage collection is a mechanism that automatically manages memory by identifying and deallocating unused memory. C++ does not have a built-in garbage collector,

but there are libraries available that provide garbage collection functionality.

Types of Garbage Collection

There are several types of garbage collection:

1. Mark-and-Sweep: This algorithm identifies reachable objects by marking them and then sweeps the heap to deallocate unreachable objects.

2. Generational Garbage Collection: This algorithm divides the heap into generations based on object lifetimes and collects garbage accordingly.

Example of Garbage Collection in C++ using the Boehm Garbage Collector

#include <gc.h>

int main() { GC_INIT();

int* ptr = new int; // Allocate memory for an integer

*ptr = 10; // Assign a value to the allocated memory

// No need to deallocate memory manually

return 0;

}

Smart Pointers in C++

Smart pointers are a type of C++ class that provides automatic memory management for dynamically allocated objects.

Smart pointers can help prevent memory leaks and make code safer.

Types of Smart Pointers

There are several types of smart pointers:

1. unique_ptr: A unique_ptr is a smart pointer that owns and manages another object. It disposes of the object when it goes out of scope.
2. shared_ptr: A shared_ptr is a smart pointer that retains shared ownership of an object. It disposes of the object when the last remaining shared_ptr to it is destroyed.

Example of Smart Pointers in C++

#include <memory>

int main() {

std::unique_ptr<int> ptr(new int); // Allocate memory for an integer

*ptr = 10; // Assign a value to the allocated memory

// No need to deallocate memory manually  

return 0;}

Thank You