( I need the output to be: Enter the number of vertices and edges: Enter edges in the format (from to weight): Enter the source vertex: Shortest paths from source vertex 2: Vertex 0: 4 Vertex 1: 3 Vertex 2: 0 the output i keep getting from the code below is Enter the number of vertices and edges: Enter edges in the format (from to weight): Enter the source vertex: Shortest paths from source vertex 2: Vertex 0: No path Vertex 1: No path Vertex 2: 0) #include <iostream> #include <vector> #include <queue> #include <climits> using namespace std; vector<int> dijkstra(int V, vector<vector<pair<int, int>>> adj, int S, vector<int>& dist) { dist.resize(V, INT_MAX); // dist[i] will hold the shortest distance from S to i vector<int> prev(V, -1); // prev[i] will hold the penultimate vertex in the shortest path from S to i // Priority queue to store vertices that are being processed priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // Initialize source vertex distance as 0 and push it to the priority queue dist[S] = 0; // Adjusted: Set distance from source to itself as 0 pq.push({0, S}); // Dijkstra's algorithm while (!pq.empty()) { int u = pq.top().second; pq.pop(); // Visit each neighbor of u for (auto& edge : adj[u]) { int v = edge.first; // neighbor vertex int weight = edge.second; // weight of the edge from u to v // If a shorter path is found, update distance and penultimate vertex if (dist[u] + weight < dist[v]) { dist[v] = dist[u] + weight; prev[v] = u; pq.push({dist[v], v}); } } } return prev; // Return the penultimate vertex array } int main() { int v, e, source; cout << "Enter the number of vertices and edges: "; cin >> v >> e; // Initialize the graph with n vertices vector<vector<pair<int, int>>> adj(v); // Read edges and weights cout << "Enter edges in the format (from to weight):" << endl; for (int i = 0; i < e; ++i) { int from, to, weight; cin >> from >> to >> weight; adj[from].push_back({to, weight}); } cout << "Enter the source vertex: "; cin >> source; // Find shortest paths from source to all vertices vector<int> dist; vector<int> prev_vertices = dijkstra(v, adj, source, dist); // Print shortest paths cout << "Shortest paths from source vertex " << source << ":\n"; for (int i = 0; i < v; ++i) { cout << "Vertex " << i << ": "; if (dist[i] == INT_MAX) { cout << "No path\n"; } else { cout << dist[i] << endl; } } return 0; }

( I need the output to be: Enter the number of vertices and edges: Enter edges in the format (from to weight): Enter the source vertex: Shortest paths from source vertex 2: Vertex 0: 4 Vertex 1: 3 Vertex 2: 0 the output i keep getting from the code below is Enter the number of vertices and edges: Enter edges in the format (from to weight): Enter the source vertex: Shortest paths from source vertex 2: Vertex 0: No path Vertex 1: No path Vertex 2: 0) #include <iostream> #include <vector> #include <queue> #include <climits> using namespace std; vector<int> dijkstra(int V, vector<vector<pair<int, int>>> adj, int S, vector<int>& dist) { dist.resize(V, INT_MAX); // dist[i] will hold the shortest distance from S to i vector<int> prev(V, -1); // prev[i] will hold the penultimate vertex in the shortest path from S to i // Priority queue to store vertices that are being processed priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // Initialize source vertex distance as 0 and push it to the priority queue dist[S] = 0; // Adjusted: Set distance from source to itself as 0 pq.push({0, S}); // Dijkstra's algorithm while (!pq.empty()) { int u = pq.top().second; pq.pop(); // Visit each neighbor of u for (auto& edge : adj[u]) { int v = edge.first; // neighbor vertex int weight = edge.second; // weight of the edge from u to v // If a shorter path is found, update distance and penultimate vertex if (dist[u] + weight < dist[v]) { dist[v] = dist[u] + weight; prev[v] = u; pq.push({dist[v], v}); } } } return prev; // Return the penultimate vertex array } int main() { int v, e, source; cout << "Enter the number of vertices and edges: "; cin >> v >> e; // Initialize the graph with n vertices vector<vector<pair<int, int>>> adj(v); // Read edges and weights cout << "Enter edges in the format (from to weight):" << endl; for (int i = 0; i < e; ++i) { int from, to, weight; cin >> from >> to >> weight; adj[from].push_back({to, weight}); } cout << "Enter the source vertex: "; cin >> source; // Find shortest paths from source to all vertices vector<int> dist; vector<int> prev_vertices = dijkstra(v, adj, source, dist); // Print shortest paths cout << "Shortest paths from source vertex " << source << ":\n"; for (int i = 0; i < v; ++i) { cout << "Vertex " << i << ": "; if (dist[i] == INT_MAX) { cout << "No path\n"; } else { cout << dist[i] << endl; } } return 0; }

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

( I need the output to be: Enter the number of vertices and edges: Enter edges in the format (from to weight): Enter the source vertex: Shortest paths from source vertex 2: Vertex 0: 4 Vertex 1: 3 Vertex 2: 0 the output i keep getting from the code below is Enter the number of vertices and edges: Enter edges in the format (from to weight): Enter the source vertex: Shortest paths from source vertex 2: Vertex 0: No path Vertex 1: No path Vertex 2: 0)

#include <iostream>

#include <vector>

#include <queue>

#include <climits>

using namespace std;

vector<int> dijkstra(int V, vector<vector<pair<int, int>>> adj, int S, vector<int>& dist) {

dist.resize(V, INT_MAX); // dist[i] will hold the shortest distance from S to i

vector<int> prev(V, -1); // prev[i] will hold the penultimate vertex in the shortest path from S to i

// Priority queue to store vertices that are being processed

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

// Initialize source vertex distance as 0 and push it to the priority queue

dist[S] = 0; // Adjusted: Set distance from source to itself as 0

pq.push({0, S});

// Dijkstra's algorithm

while (!pq.empty()) {

int u = pq.top().second;

pq.pop();

// Visit each neighbor of u

for (auto& edge : adj[u]) {

int v = edge.first; // neighbor vertex

int weight = edge.second; // weight of the edge from u to v

// If a shorter path is found, update distance and penultimate vertex

if (dist[u] + weight < dist[v]) {

dist[v] = dist[u] + weight;

prev[v] = u;

pq.push({dist[v], v});

}

return prev; // Return the penultimate vertex array

}

int main() {

int v, e, source;

cout << "Enter the number of vertices and edges: ";

cin >> v >> e;

// Initialize the graph with n vertices

vector<vector<pair<int, int>>> adj(v);

// Read edges and weights

cout << "Enter edges in the format (from to weight):" << endl;

for (int i = 0; i < e; ++i) {

int from, to, weight;

cin >> from >> to >> weight;

adj[from].push_back({to, weight});

}

cout << "Enter the source vertex: ";

cin >> source;

// Find shortest paths from source to all vertices

vector<int> dist;

vector<int> prev_vertices = dijkstra(v, adj, source, dist);

// Print shortest paths

cout << "Shortest paths from source vertex " << source << ":\n";

for (int i = 0; i < v; ++i) {

cout << "Vertex " << i << ": ";

if (dist[i] == INT_MAX) {

cout << "No path\n";

} else {

cout << dist[i] << endl;

}

return 0;

}

Expert Solution

Step by step

Solved in 2 steps with 1 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.