There are several ways to store the data for multiple objectives in shortest-path search algorithms in C++.
One way is to use a data structure such as a priority queue or a heap that allows you to store the data in a sorted manner, with the elements being ordered according to their cost.
For example, use a std::priority_queue from the C++ Standard Template Library (STL) to store the data for your shortest path search algorithm. The priority queue allows you to insert elements with a certain priority, and it will automatically maintain the queue in a sorted order based on the priority of the elements.
Here is an example of how to use a priority queue to store the data for a shortest-path search algorithm in C++ and Java:
C++
// C++ code for the above approach:#include <iostream>#include <queue>#include <vector>struct Node { int id; int cost;};struct Compare { bool operator()(const Node& lhs, const Node& rhs) { return lhs.cost > rhs.cost; }};std::priority_queue<Node, std::vector<Node>, Compare> pq;// Driver Codeint main(){ // Insert some nodes into the priority queue pq.push({ 1, 5 }); pq.push({ 2, 2 }); pq.push({ 3, 8 }); pq.push({ 4, 1 }); // The priority queue is now sorted // according to the cost of the nodes, // with the node having the lowest // cost being at the front of the queue while (!pq.empty()) { Node node = pq.top(); pq.pop(); std::cout << "Node ID: " << node.id << ", Cost: " << node.cost << std::endl; } return 0;} |
Java
// Java code for the above approach:import java.util.*;class Node { int id; int cost; Node(int id, int cost) { this.id = id; this.cost = cost; }}class Compare implements Comparator<Node> { public int compare(Node lhs, Node rhs) { return lhs.cost - rhs.cost; }}class Main { static PriorityQueue<Node> pq = new PriorityQueue<Node>(new Compare()); public static void main(String[] args) { // Insert some nodes into the priority queue pq.add(new Node(1, 5)); pq.add(new Node(2, 2)); pq.add(new Node(3, 8)); pq.add(new Node(4, 1)); // The priority queue is now sorted // according to the cost of the nodes, // with the node having the lowest // cost being at the front of the queue while (!pq.isEmpty()) { Node node = pq.poll(); System.out.println("Node ID: " + node.id + ", Cost: " + node.cost); } }} |
Python3
# Python code for the above approachimport queueclass Node: def __init__(self, id, cost): self.id = id self.cost = cost # Define the less than operator for comparison def __lt__(self, other): return self.cost < other.costpq = queue.PriorityQueue()# Insert some nodes into the priority queuepq.put(Node(1, 5))pq.put(Node(2, 2))pq.put(Node(3, 8))pq.put(Node(4, 1))# The priority queue is now sorted# according to the cost of the nodes,# with the node having the lowest# cost being at the front of the queuewhile not pq.empty(): node = pq.get() print("Node ID: {}, Cost: {}".format(node.id, node.cost))# This code is contributed by princekumaras |
Javascript
// Javascript program for the above approachclass Node { constructor(id, cost) { this.id = id; this.cost = cost; } // Define the less than operator for comparison // In JavaScript, the comparison function is passed as a parameter to the // sort() method, so this method is not needed. // Instead, we will use an arrow function later to define the comparison function. // __lt__(self, other) { // return self.cost < other.cost; // }}const pq = [];// Insert some nodes into the priority queuepq.push(new Node(1, 5));pq.push(new Node(2, 2));pq.push(new Node(3, 8));pq.push(new Node(4, 1));// The priority queue is now sorted// according to the cost of the nodes,// with the node having the lowest// cost being at the front of the queuepq.sort((a, b) => a.cost - b.cost);while (pq.length > 0) { const node = pq.shift(); console.log(`Node ID: ${node.id}, Cost: ${node.cost}`);}// This code is contributed by adityashatmfh |
C#
// C# code for the above approach:using System;using System.Collections.Generic;public class Node { public int id; public int cost; public Node(int id, int cost) { this.id = id; this.cost = cost; }}public class NodeComparer : IComparer<Node> { public int Compare(Node lhs, Node rhs) { return lhs.cost - rhs.cost; }}public class Program { static SortedSet<Node> pq = new SortedSet<Node>(new NodeComparer()); public static void Main(string[] args) { // Insert some nodes into the priority queue pq.Add(new Node(1, 5)); pq.Add(new Node(2, 2)); pq.Add(new Node(3, 8)); pq.Add(new Node(4, 1)); // The priority queue is now sorted // according to the cost of the nodes, // with the node having the lowest // cost being at the front of the queue while (pq.Count > 0) { Node node = pq.Min; pq.Remove(node); Console.WriteLine("Node ID: " + node.id + ", Cost: " + node.cost); } }}// Contributed by adityasharmadev01 |
Node ID: 4, Cost: 1 Node ID: 2, Cost: 2 Node ID: 1, Cost: 5 Node ID: 3, Cost: 8
Time Complexity: O(N*log(N))
Auxiliary Space: O(1)
Alternatively, you could use a different data structure, such as a std::map or a std::unordered_map, to store the data for your shortest path search algorithm. These data structures allow you to store the data in a key-value format, where the key is the node ID and the value is the cost of the node. You can then iterate through the map and extract the nodes in the order that you desire.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
