script.js

// Store graph as adjacency list
let graph = {};
let nodes = [];
let edges = [];

// Function to add a node
function addNode() {
    let nodeName = prompt("Enter node name:");
    if (!nodeName || nodes.includes(nodeName)) {
        alert("Invalid or duplicate node!");
        return;
    }
    nodes.push(nodeName);
    graph[nodeName] = {};
    drawGraph();
}

// Function to add an edge with weight
function addEdge() {
    let nodeA = prompt("Enter first node:");
    let nodeB = prompt("Enter second node:");
    let weight = parseInt(prompt("Enter weight:"), 10);

    if (!nodes.includes(nodeA) || !nodes.includes(nodeB) || isNaN(weight) || nodeA === nodeB) {
        alert("Invalid input or self-loop!");
        return;
    }

    graph[nodeA][nodeB] = weight;
    graph[nodeB][nodeA] = weight; // Undirected Graph
    edges.push({ from: nodeA, to: nodeB, weight: weight });
    drawGraph();
}

// Priority Queue (Min-Heap) for Dijkstra
class PriorityQueue {
    constructor() {
        this.values = [];
    }
    enqueue(val, priority) {
        this.values.push({ val, priority });
        this.values.sort((a, b) => a.priority - b.priority);
    }
    dequeue() {
        return this.values.shift();
    }
}

// Dijkstra's Algorithm
function dijkstra(start) {
    let distances = {};
    let pq = new PriorityQueue();
    let previous = {};

    nodes.forEach(node => {
        distances[node] = Infinity;
        previous[node] = null;
    });

    distances[start] = 0;
    pq.enqueue(start, 0);

    while (pq.values.length) {
        let { val: smallest } = pq.dequeue();

        for (let neighbor in graph[smallest]) {
            let newDist = distances[smallest] + graph[smallest][neighbor];

            if (newDist < distances[neighbor]) {
                distances[neighbor] = newDist;
                previous[neighbor] = smallest;
                pq.enqueue(neighbor, newDist);
            }
        }
    }

    return { distances, previous };
}

// Run Dijkstra's Algorithm
function runDijkstra() {
    let startNode = prompt("Enter starting node:");
    if (!nodes.includes(startNode)) {
        alert("Node does not exist!");
        return;
    }

    let result = dijkstra(startNode);
    displayResults(result, startNode);
}

// Display shortest paths
function displayResults(result, startNode) {
    let output = `Shortest paths from ${startNode}:\n`;
    for (let node in result.distances) {
        output += `To ${node}: Distance = ${result.distances[node]} | Path: ${tracePath(result.previous, node)}\n`;
    }
    alert(output);
}

// Trace path from previous nodes
function tracePath(previous, node) {
    let path = [];
    while (node) {
        path.unshift(node);
        node = previous[node];
    }
    return path.join(" → ");
}

// Reset graph
function resetGraph() {
    graph = {};
    nodes = [];
    edges = [];
    document.getElementById("graphContainer").innerHTML = "";
}

// Draw graph using Canvas
function drawGraph() {
    let container = document.getElementById("graphContainer");
    container.innerHTML = "";

    let canvas = document.createElement("canvas");
    canvas.width = 800;  // Increase width
    canvas.height = 600; // Increase height

    container.appendChild(canvas);

    let ctx = canvas.getContext("2d");

    // Improved Node Positioning
    let positions = {};
    let angleStep = (2 * Math.PI) / nodes.length;
    let centerX = canvas.width / 2;
    let centerY = canvas.height / 2;
    let radius = Math.min(canvas.width, canvas.height) / 2.5;

    nodes.forEach((node, index) => {
        positions[node] = {
            x: centerX + radius * Math.cos(index * angleStep),
            y: centerY + radius * Math.sin(index * angleStep)
        };
    });

    // Draw edges with curves to avoid overlap
    edges.forEach((edge, index) => {
        let { from, to, weight } = edge;
        let posA = positions[from];
        let posB = positions[to];

        ctx.beginPath();
        let midX = (posA.x + posB.x) / 2;
        let midY = (posA.y + posB.y) / 2;

        // Curve edges if needed
        let controlX = midX + (index % 2 === 0 ? 20 : -20);
        let controlY = midY + (index % 2 === 0 ? -20 : 20);

        ctx.moveTo(posA.x, posA.y);
        ctx.quadraticCurveTo(controlX, controlY, posB.x, posB.y);
        ctx.strokeStyle = "black";
        ctx.lineWidth = 2;
        ctx.stroke();

        // Display weights near the curve
        ctx.font = "bold 20px Arial"; // Increase font size
        ctx.fillStyle = "red";
        ctx.textAlign = "center";
        ctx.textBaseline = "middle";
        ctx.fillText(weight, (posA.x + posB.x) / 2, (posA.y + posB.y) / 2 - 10);

    });

    // Draw nodes
    nodes.forEach(node => {
        let pos = positions[node];

        ctx.beginPath();
        ctx.arc(pos.x, pos.y, 20, 0, Math.PI * 2);
        ctx.fillStyle = "lightblue";
        ctx.fill();
        ctx.strokeStyle = "black";
        ctx.stroke();

        ctx.fillStyle = "black";
        ctx.fillText(node, pos.x - 5, pos.y + 5);
    });
}