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

Operations Research : Applications and Algorithms
Operations Research : Applications and Algorithms
4th Edition
ISBN:9780534380588
Author:Wayne L. Winston
Publisher:Wayne L. Winston
Chapter18: Deterministic Dynamic Programming
Section18.4: Resource-allocation Problems
Problem 3P
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
Recommended textbooks for you
Operations Research : Applications and Algorithms
Operations Research : Applications and Algorithms
Computer Science
ISBN:
9780534380588
Author:
Wayne L. Winston
Publisher:
Brooks Cole
EBK JAVA PROGRAMMING
EBK JAVA PROGRAMMING
Computer Science
ISBN:
9781337671385
Author:
FARRELL
Publisher:
CENGAGE LEARNING - CONSIGNMENT
Systems Architecture
Systems Architecture
Computer Science
ISBN:
9781305080195
Author:
Stephen D. Burd
Publisher:
Cengage Learning
Np Ms Office 365/Excel 2016 I Ntermed
Np Ms Office 365/Excel 2016 I Ntermed
Computer Science
ISBN:
9781337508841
Author:
Carey
Publisher:
Cengage
LINUX+ AND LPIC-1 GDE.TO LINUX CERTIF.
LINUX+ AND LPIC-1 GDE.TO LINUX CERTIF.
Computer Science
ISBN:
9781337569798
Author:
ECKERT
Publisher:
CENGAGE L
Programming Logic & Design Comprehensive
Programming Logic & Design Comprehensive
Computer Science
ISBN:
9781337669405
Author:
FARRELL
Publisher:
Cengage
SEE MORE TEXTBOOKS