Final Project code

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int minDistance(vector<int>& dist, vector<bool>& visited, int n) {
    int min = INT_MAX, minIndex = -1;
    for (int i = 0; i <= n; i++) {
        if (!visited[i] && dist[i] <= min) {
            min = dist[i];
            minIndex = i;
        }
    }
    return minIndex;
}

void printPath(vector<int>& parent, int node) {
    if (parent[node] == -1) {
        cout << node;
        return;
    }
    printPath(parent, parent[node]);
    cout << " -> " << node;
}

void dijkstra(vector<vector<pair<int,int>>>& graph, int n) {
    vector<int> dist(n + 1, INT_MAX);
    vector<bool> visited(n + 1, false);
    vector<int> parent(n + 1, -1);

    dist[0] = 0;

    for (int count = 0; count <= n; count++) {
        int u = minDistance(dist, visited, n);
        if (u == -1) break;
        visited[u] = true;

        for (auto edge : graph[u]) {
            int v = edge.first;
            int w = edge.second;
            if (!visited[v] && dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                parent[v] = u;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << "Customer " << i << ": ";
        if (dist[i] == INT_MAX) {
            cout << "Not reachable" << endl;
        } else {
            cout << "Minimum Distance = " << dist[i] << ", Path = ";
            printPath(parent, i);
            cout << endl;
        }
    }
}

int main() {
    int n, e;
    cout << "Enter number of customers and roads: ";
    cin >> n >> e;

    vector<vector<pair<int,int>>> graph(n + 1);

    cout << "Enter roads (u v w):" << endl;
    for (int i = 0; i < e; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }

    dijkstra(graph, n);

    return 0;
}