Homework Help is Here – Start Your Trial Now!
Engineering
Computer Science
% 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
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
icon
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
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
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 2 steps

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Similar questions
  • SEE MORE QUESTIONS
Recommended textbooks for you
Database System Concepts
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)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education
SEE MORE TEXTBOOKS