Homework Help is Here – Start Your Trial Now!
Engineering
Computer Science
* LAST RUN on 4/18/2024, 10:13:27 AM Check 1 failed Output: Dijkstra.cpp: In function 'int main()': Dijkstra.cpp:82:17: error: 'dist' was not decla 82 | if (dist[i] == INT_MAX) { Expected: Enter the number of vertices and edges: Enter € Enter the source vertex: Shortest paths from sc Vertex 0: 0 Vertex 1: 9 Check 2 failed Output: Dijkstra.cpp: In function 'int main()': Dijkstra.cpp:82:17: error: 'dist' was not decla 82 | | if (dist[i] == INT_MAX) { 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, 10:13:27 AM Check 1 failed Output: Dijkstra.cpp: In function 'int main()': Dijkstra.cpp:82:17: error: 'dist' was not decla 82 | if (dist[i] == INT_MAX) { Expected: Enter the number of vertices and edges: Enter € Enter the source vertex: Shortest paths from sc Vertex 0: 0 Vertex 1: 9 Check 2 failed Output: Dijkstra.cpp: In function 'int main()': Dijkstra.cpp:82:17: error: 'dist' was not decla 82 | | if (dist[i] == INT_MAX) { 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

Help me fix my error in my code the expected output is in the picture.

My Code:   

#include <iostream>
#include <vector>
#include <queue>
#include <climits> // Include the <climits> header for INT_MAX

using namespace std;

vector<int> dijkstra(int V, vector<vector<pair<int, int>>> adj, int S) {
    vector<int> dist(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;
    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
}

//DO NOT edit the code below.
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}); // Only add edge from 'from' to 'to'
    }

    cout << "Enter the source vertex: ";
    cin >> source;

    // Find shortest paths from source to all vertices
    vector<int> prev_vertices = dijkstra(v, adj, source);

    // Print shortest paths
    cout << "Shortest paths from source vertex " << source << ":\n";
    for (int i = 0; i < v; ++i) {
        cout << "Vertex " << i << ": ";
        if (prev_vertices[i] == -1) {
            if (i == source) {
                cout << "0\n";
            } else {
                cout << "No path\n";
            }
        } else {
            // Reconstruct the shortest path
            vector<int> path;
            int current = i;
            while (current != -1) {
                path.push_back(current);
                current = prev_vertices[current];
            }
            if (dist[i] == INT_MAX) {
                cout << "No path\n";
            } else {
                cout << "Distance: " << dist[i] << ", Path: ";
                for (int j = path.size() - 1; j >= 0; --j) {
                    cout << path[j] << (j == 0 ? "\n" : " -> ");
                }
            }
        }
    }

    return 0;
}
* LAST RUN on 4/18/2024, 10:13:27 AM Check 1 failed Output: Dijkstra.cpp: In function 'int main()': Dijkstra.cpp:82:17: error: 'dist' was not decla 82 | if (dist[i] == INT_MAX) { Expected: Enter the number of vertices and edges: Enter € Enter the source vertex: Shortest paths from sc Vertex 0: 0 Vertex 1: 9 Check 2 failed Output: Dijkstra.cpp: In function 'int main()': Dijkstra.cpp:82:17: error: 'dist' was not decla 82 | | if (dist[i] == INT_MAX) { 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, 10:13:27 AM Check 1 failed Output: Dijkstra.cpp: In function 'int main()': Dijkstra.cpp:82:17: error: 'dist' was not decla 82 | if (dist[i] == INT_MAX) { Expected: Enter the number of vertices and edges: Enter € Enter the source vertex: Shortest paths from sc Vertex 0: 0 Vertex 1: 9 Check 2 failed Output: Dijkstra.cpp: In function 'int main()': Dijkstra.cpp:82:17: error: 'dist' was not decla 82 | | if (dist[i] == INT_MAX) { 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