% LAST RUN on 4/18/2024, 12:38:33 PM Check 1 passed Check 2 failed Output: Enter the number of vertices and edges: Enter € Enter the source vertex: Shortest paths from sc Vertex : No path Vertex 1: No path Vertex 2: 0 Expected: Enter the number of vertices and edges: Enter € Enter the source vertex: Shortest paths from sc Vertex 0: 4 Vertex 1: 3 Vertex 2: 0
% LAST RUN on 4/18/2024, 12:38:33 PM Check 1 passed Check 2 failed Output: Enter the number of vertices and edges: Enter € Enter the source vertex: Shortest paths from sc Vertex : No path Vertex 1: No path Vertex 2: 0 Expected: Enter the number of vertices and edges: Enter € Enter the source vertex: Shortest paths from sc Vertex 0: 4 Vertex 1: 3 Vertex 2: 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
Related questions
Question
(I need help getting the expected output!)
#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;
}
![%
LAST RUN on 4/18/2024, 12:38:33 PM
Check 1 passed
Check 2 failed
Output:
Enter the number of vertices and edges: Enter €
Enter the source vertex: Shortest paths from sc
Vertex : No path
Vertex 1: No path
Vertex 2: 0
Expected:
Enter the number of vertices and edges: Enter €
Enter the source vertex: Shortest paths from sc
Vertex 0: 4
Vertex 1: 3
Vertex 2: 0](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fb27ad09a-811a-4663-a78e-f7b328b928a0%2F4e184b51-d7c5-4250-afc7-272d9899193d%2Fsazs0ys_processed.png&w=3840&q=75)
Transcribed Image Text:%
LAST RUN on 4/18/2024, 12:38:33 PM
Check 1 passed
Check 2 failed
Output:
Enter the number of vertices and edges: Enter €
Enter the source vertex: Shortest paths from sc
Vertex : No path
Vertex 1: No path
Vertex 2: 0
Expected:
Enter the number of vertices and edges: Enter €
Enter the source vertex: Shortest paths from sc
Vertex 0: 4
Vertex 1: 3
Vertex 2: 0
Expert Solution
![](/static/compass_v2/shared-icons/check-mark.png)
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
![Blurred answer](/static/compass_v2/solution-images/blurred-answer.jpg)
Recommended textbooks for you
![Database System Concepts](https://www.bartleby.com/isbn_cover_images/9780078022159/9780078022159_smallCoverImage.jpg)
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
![Starting Out with Python (4th Edition)](https://www.bartleby.com/isbn_cover_images/9780134444321/9780134444321_smallCoverImage.gif)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
![Digital Fundamentals (11th Edition)](https://www.bartleby.com/isbn_cover_images/9780132737968/9780132737968_smallCoverImage.gif)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
![Database System Concepts](https://www.bartleby.com/isbn_cover_images/9780078022159/9780078022159_smallCoverImage.jpg)
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
![Starting Out with Python (4th Edition)](https://www.bartleby.com/isbn_cover_images/9780134444321/9780134444321_smallCoverImage.gif)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
![Digital Fundamentals (11th Edition)](https://www.bartleby.com/isbn_cover_images/9780132737968/9780132737968_smallCoverImage.gif)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
![C How to Program (8th Edition)](https://www.bartleby.com/isbn_cover_images/9780133976892/9780133976892_smallCoverImage.gif)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
![Database Systems: Design, Implementation, & Manag…](https://www.bartleby.com/isbn_cover_images/9781337627900/9781337627900_smallCoverImage.gif)
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
![Programmable Logic Controllers](https://www.bartleby.com/isbn_cover_images/9780073373843/9780073373843_smallCoverImage.gif)
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education