#include <iostream.h>
#include <conio.h>

void main()
{
    int rowIndex, colIndex;   // Loop counters for matrix traversal

    // --- Read the number of vertices ---
    int vertexCount;
    cout << "\n Enter vertex count: ";
    cin >> vertexCount;

    // --- Initialise the cost matrix to -1 (no edge) ---
    int costMatrix[15][15];
    for (rowIndex = 0; rowIndex < vertexCount; rowIndex++)
    {
        for (colIndex = 0; colIndex < vertexCount; colIndex++)
        {
            costMatrix[rowIndex][colIndex] = -1;
        }
    }

    // --- Read edge weights from the user ---
    // Self-loops are set to 0; for each pair (u,v) with u != v,
    // the user enters the edge weight or -1 for no direct connection.
    cout << "\n Enter weight of edges:\n";
    for (rowIndex = 0; rowIndex < vertexCount; rowIndex++)
    {
        for (colIndex = 0; colIndex < vertexCount; colIndex++)
        {
            if (rowIndex == colIndex)
                costMatrix[rowIndex][colIndex] = 0;   // Distance from a vertex to itself is 0

            if (costMatrix[rowIndex][colIndex] == -1) // Only prompt for unfilled entries
            {
                cout << "\n " << rowIndex << " to " << colIndex << " : ";
                cin >> costMatrix[rowIndex][colIndex];
            }
        }
    }

    // --- Display the cost matrix ---
    cout << "\n Entered Cost Matrix:";
    cout << "\n";
    for (rowIndex = 0; rowIndex < vertexCount; rowIndex++)
    {
        for (colIndex = 0; colIndex < vertexCount; colIndex++)
        {
            cout << costMatrix[rowIndex][colIndex] << " ";
        }
        cout << "\n";
    }

    // --- Initialise Dijkstra data structures ---
    int shortestDist[15];   // shortestDist[v] = best known distance from source to v
    int parentVertex[15];   // parentVertex[v] = predecessor of v on the shortest path
    int visited[15];        // visited[v] = 1 once v has been finalised

    for (rowIndex = 0; rowIndex < vertexCount; rowIndex++)
    {
        shortestDist[rowIndex] = 999;    // Infinity
        parentVertex[rowIndex] = -1;     // No parent yet
        visited[rowIndex]      = 0;      // Not yet visited
    }

    // --- Read the source vertex ---
    int sourceVertex;
    cout << "\n Enter Starting vertex: ";
    cin >> sourceVertex;

    // Distance from source to itself is 0
    shortestDist[sourceVertex] = 0;
    parentVertex[sourceVertex] = -1;
    visited[sourceVertex]      = 1;

    int currentVertex = sourceVertex;   // Vertex being processed in the current iteration
    int smallestDist  = 999;            // Tracks the minimum distance among unvisited vertices

    // --- Main Dijkstra loop: repeat (vertexCount - 1) times ---
    for (rowIndex = 0; rowIndex < vertexCount - 1; rowIndex++)
    {
        // Relax all neighbours of currentVertex
        for (colIndex = 0; colIndex < vertexCount; colIndex++)
        {
            if (costMatrix[currentVertex][colIndex] > 0)  // Edge exists
            {
                if (shortestDist[colIndex] > shortestDist[currentVertex] + costMatrix[currentVertex][colIndex])
                {
                    shortestDist[colIndex] = shortestDist[currentVertex] + costMatrix[currentVertex][colIndex];
                    parentVertex[colIndex] = currentVertex;
                }
            }
        }

        // Mark currentVertex as visited
        visited[currentVertex] = 1;
        smallestDist = 999;

        // Pick the unvisited vertex with the smallest known distance
        for (int scanIndex = 0; scanIndex < vertexCount; scanIndex++)
        {
            if (visited[scanIndex] != 1 && shortestDist[scanIndex] < smallestDist)
            {
                smallestDist  = shortestDist[scanIndex];
                currentVertex = scanIndex;
            }
        }

        smallestDist = 999;  // Reset for next iteration
    }

    // --- Display the shortest path table ---
    cout << "\n Shortest Path:";
    cout << "\n Vertex\tDist\tParent\n";
    for (rowIndex = 0; rowIndex < vertexCount; rowIndex++)
    {
        cout << rowIndex << "\t" << shortestDist[rowIndex] << "\t" << parentVertex[rowIndex] << "\n";
    }

    getch();
}