// C Program to Implement Shortest Path Algorithm
#include <limits.h>
#include <stdio.h>
// Number of vertices in the graph
#define V 5

// Function to find the vertex with the minimum distance
// value from the set of vertices not yet included in the
// shortest path tree
int findminDistance(int dist[], int included[])
{
    int min = INT_MAX, min_index;

    // Traverse all vertices to find the vertex with the
    // minimum distance value
    for (int v = 0; v < V; v++) {
        if (included[v] == 0 && dist[v] <= min) {
            min = dist[v];
            min_index = v;
        }
    }
    return min_index;
}

// Function to print the constructed distance array
void printSolution(int dist[])
{
    printf("Vertex \t Distance from Source\n");
    for (int i = 0; i < V; i++) {
        printf("%d \t\t %d\n", i, dist[i]);
    }
}

// Function that implements Dijkstra's algorithm
void DijkstrasAlgo(int graph[V][V], int src)
{
    // Array to store the minimum distance from source node
    // to the current node
    int dist[V];
    // Array to keep track of included nodes
    int included[V];

    // Initialize all distances as INFINITE and included as
    // false
    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        included[i] = 0;
    }

    // Distance of source vertex from itself is always 0
    dist[src] = 0;

    // Find the shortest path for all vertices
    for (int count = 0; count < V - 1; count++) {
        // Pick the minimum distance vertex from the set of
        // vertices not yet processed
        int u = findminDistance(dist, included);

        // Mark the selected vertex as included
        included[u] = 1;

        // Update the distance of all the adjacent vertices
        // of the selected vertex
        for (int v = 0; v < V; v++) {
            // update dist[v] if it is already note included
            // and the current distance is less then it's
            // original distance
            if (!included[v] && graph[u][v]
                && dist[u] != INT_MAX
                && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    // Print the constructed distance array
    printSolution(dist);
}

int main()
{

    int graph[V][V] = {
        { 0, 1, 4, 6, 1 }, // Node A (0) connections
        { 1, 0, 0, 2, 0 }, // Node B (1) connections
        { 4, 0, 0, 0, 1 }, // Node C (2) connections
        { 6, 2, 0, 0, 5 }, // Node D (3) connections
        { 1, 0, 1, 5, 0 } // Node E (4) connections
    };

    // Perform Dijkstra's algorithm starting from vertex 0
    // (Node A)
    DijkstrasAlgo(graph, 0);

    return 0;
}

// C program for Bellman Ford algorithm
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

// Structure to represent an edge in the graph
struct Edge {
    int src, dest, weight;
};

// Structure to represent a graph
struct Graph {
    // V: Number of vertices, E: Number of edges
    int V, E;
    // Array of edges
    struct Edge* edge;
};

// Function to create a graph with V vertices and E edges
struct Graph* createGraph(int V, int E)
{
    struct Graph* graph
        = (struct Graph*)malloc(sizeof(struct Graph));
    graph->V = V;
    graph->E = E;
    graph->edge = (struct Edge*)malloc(
        graph->E * sizeof(struct Edge));
    return graph;
}

// Function to run Bellman-Ford algorithm from a source
// vertex src
void BellmanFord(struct Graph* graph, int src)
{
    // Number of vertices in the graph
    int V = graph->V;
    // Number of edges in the graph
    int E = graph->E;
    // Array to hold the shortest distance from src to each
    // vertex
    int dist[V];

    // Step 1: Initialize distances from src to all other
    // vertices as INFINITE
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX;
    dist[src] = 0;

    // Step 2: Relax all edges |V| - 1 times.
    // A simple shortest path from src to any other vertex
    // can have at most |V| - 1 edges
    for (int i = 1; i <= V - 1; i++) {
        for (int j = 0; j < E; j++) {
            int u = graph->edge[j].src;
            int v = graph->edge[j].dest;
            int weight = graph->edge[j].weight;
            if (dist[u] != INT_MAX
                && dist[u] + weight < dist[v])
                dist[v] = dist[u] + weight;
        }
    }

    // Step 3: Check for negative-weight cycles.
    // The above step guarantees shortest distances if the
    // graph doesn't contain negative weight cycles. If we
    // get a shorter path, then there is a cycle.
    for (int i = 0; i < E; i++) {
        int u = graph->edge[i].src;
        int v = graph->edge[i].dest;
        int weight = graph->edge[i].weight;
        if (dist[u] != INT_MAX
            && dist[u] + weight < dist[v]) {
            printf("Graph contains negative weight cycle");
            // If negative weight cycle is detected, return
            return;
        }
    }

    // Print the calculated shortest distances
    printf("Vertex   Distance from Source\n");
    for (int i = 0; i < V; i++)
        printf("%d \t\t %d\n", i, dist[i]);
}

// Main function to run the Bellman-Ford algorithm
int main()
{
    // Number of vertices
    int V = 5;
    // Number of edges
    int E = 8;
    struct Graph* graph = createGraph(V, E);

    // Adding edges to the graph
    // Edge 0-1
    graph->edge[0].src = 0;
    graph->edge[0].dest = 1;
    graph->edge[0].weight = -1;

    // Edge 0-2
    graph->edge[1].src = 0;
    graph->edge[1].dest = 2;
    graph->edge[1].weight = 4;

    // Edge 1-2
    graph->edge[2].src = 1;
    graph->edge[2].dest = 2;
    graph->edge[2].weight = 3;

    // Edge 1-3
    graph->edge[3].src = 1;
    graph->edge[3].dest = 3;
    graph->edge[3].weight = 2;

    // Edge 1-4
    graph->edge[4].src = 1;
    graph->edge[4].dest = 4;
    graph->edge[4].weight = 2;

    // Edge 3-2
    graph->edge[5].src = 3;
    graph->edge[5].dest = 2;
    graph->edge[5].weight = 5;

    // Edge 3-1
    graph->edge[6].src = 3;
    graph->edge[6].dest = 1;
    graph->edge[6].weight = 1;

    // Edge 4-3
    graph->edge[7].src = 4;
    graph->edge[7].dest = 3;
    graph->edge[7].weight = -3;

    // Run Bellman-Ford algorithm from vertex 0
    BellmanFord(graph, 0);

    return 0;
}

// C Program for  A* Search Algorithm

#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#define MAX_NODES 1000
#define MAX_SUCCESSORS 8

// Structure to represent a point in the grid
typedef struct {
    int x, y;
} Point;

// Structure to represent a node in the search tree
typedef struct Node {
    // Position of the node in the grid
    Point pos;
    // Cost from the start node to this node
    int g;
    // Heuristic cost from this node to the goal node
    int h;
    // Total cost (g + h)
    int f;
    // Pointer to the parent node
    struct Node* parent;
} Node;

// Structure to represent a list of nodes (either open or
// closed)
typedef struct {
    // Array of node pointers
    Node* nodes[MAX_NODES];
    // Current size of the list
    int size;
} List;

// Function to create a new node
Node* createNode(Point pos, Node* parent, int g, int h)
{
    Node* node = (Node*)malloc(sizeof(Node));
    node->pos = pos;
    node->parent = parent;
    node->g = g;
    node->h = h;
    node->f = g + h;
    return node;
}

// Function to add a node to a list
void addToList(List* list, Node* node)
{
    list->nodes[list->size++] = node;
}

// Function to get the node with the lowest 'f' value from a
// list
Node* getLowestF(List* list)
{
    int lowestIndex = 0;
    for (int i = 1; i < list->size; i++) {
        if (list->nodes[i]->f
            < list->nodes[lowestIndex]->f) {
            lowestIndex = i;
        }
    }
    Node* node = list->nodes[lowestIndex];
    list->nodes[lowestIndex] = list->nodes[--list->size];
    return node;
}

// Function to check if a point is in a list
bool isInList(List* list, Point pos)
{
    for (int i = 0; i < list->size; i++) {
        if (list->nodes[i]->pos.x == pos.x
            && list->nodes[i]->pos.y == pos.y) {
            return true;
        }
    }
    return false;
}

// Heuristic function (Manhattan distance)
int heuristic(Point a, Point b)
{
    return abs(a.x - b.x) + abs(a.y - b.y);
}

// A* Search Algorithm implementation
Point* aStar(int grid[10][10], Point start, Point goal)
{
    // List of nodes to be evaluated
    List openList = { 0 };
    // List of nodes already evaluated
    List closedList = { 0 };

    // Add the start node to the open list
    addToList(
        &openList,
        createNode(start, NULL, 0, heuristic(start, goal)));

    // Main loop
    while (openList.size > 0) {
        // Get the node with the lowest 'f' value
        Node* current = getLowestF(&openList);

        // Check if the goal is reached
        if (current->pos.x == goal.x
            && current->pos.y == goal.y) {
            // Path found, reconstruct and return
            int pathLength = 0;
            Node* pathNode = current;
            while (pathNode) {
                pathLength++;
                pathNode = pathNode->parent;
            }

            Point* path = (Point*)malloc(pathLength
                                         * sizeof(Point));
            pathNode = current;
            for (int i = pathLength - 1; i >= 0; i--) {
                path[i] = pathNode->pos;
                pathNode = pathNode->parent;
            }
            // Return the found path
            return path;
        }

        // Move the current node to the closed list
        addToList(&closedList, current);

        // Generate successors (8 possible movements)
        Point successors[MAX_SUCCESSORS]
            = { { current->pos.x + 1, current->pos.y },
                { current->pos.x - 1, current->pos.y },
                { current->pos.x, current->pos.y + 1 },
                { current->pos.x, current->pos.y - 1 },
                { current->pos.x + 1, current->pos.y + 1 },
                { current->pos.x + 1, current->pos.y - 1 },
                { current->pos.x - 1, current->pos.y + 1 },
                { current->pos.x - 1,
                  current->pos.y - 1 } };

        // Evaluate each successor
        for (int i = 0; i < MAX_SUCCESSORS; i++) {
            Point successor = successors[i];

            // Check if the successor is within the grid and
            // not an obstacle
            if (successor.x < 0 || successor.x >= 10
                || successor.y < 0 || successor.y >= 10
                || grid[successor.x][successor.y] == 1
                || isInList(&closedList, successor)) {
                continue;
            }
            // Increment the cost
            int newG = current->g + 1;
            // Calculate the heuristic
            int newH = heuristic(successor, goal);
            // Calculate the total cost
            int newF = newG + newH;

            // Check if this path is better than any
            // previously found path
            if (!isInList(&openList, successor)
                || newF < current->f) {
                addToList(
                    &openList,
                    createNode(successor, current, newG,
                               newH)); // Add to open list
            }
        }
    }
    // No path found
    return NULL;
}

int main()
{
    // Grid with obstacles
    int grid[10][10] = { { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                         { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                         { 0, 0, 0, 0, 1, 1, 1, 0, 0, 0 },
                         { 0, 0, 0, 0, 1, 0, 1, 0, 0, 0 },
                         { 0, 0, 0, 0, 1, 0, 1, 0, 0, 0 },
                         { 0, 0, 0, 0, 1, 0, 1, 0, 0, 0 },
                         { 0, 0, 0, 0, 1, 0, 1, 0, 0, 0 },
                         { 0, 0, 0, 0, 1, 0, 1, 0, 0, 0 },
                         { 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 },
                         { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } };
    // Start point
    Point start = { 0, 0 };
    // Goal point
    Point goal = { 9, 9 };

    // Run A* algorithm
    Point* path = aStar(grid, start, goal);

    // Print the result
    if (path) {
        printf("Path found:\n");
        for (int i = 0;
             path[i].x != goal.x || path[i].y != goal.y;
             i++) {
            printf("(%d,%d) -> ", path[i].x, path[i].y);
        }
        printf("(%d,%d)\n", goal.x, goal.y);
        // Free allocated memory for the path
        free(path);
    }
    else {
        printf("No path found.\n");
    }

    return 0;
}

// C Program for  Floyd-Warshall Algorithm
#include <limits.h>
#include <stdio.h>

// Number of vertices in the graph
#define V 4
#define INF INT_MAX

// Function to print the solution matrix
void printSolution(int dist[][V])
{
    printf("Shortest distances between every pair of "
           "vertices:\n");
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (dist[i][j] == INF)
                printf("%7s", "INF");
            else
                printf("%7d", dist[i][j]);
        }
        printf("\n");
    }
}

// Function to implement the Floyd-Warshall algorithm
void floydWarshall(int graph[][V])
{
    int dist[V][V];

    // Initialize the solution matrix same as the input
    // graph matrix.
    for (int i = 0; i < V; i++)
        for (int j = 0; j < V; j++)
            dist[i][j] = graph[i][j];

    // Add all vertices one by one to the set of
    // intermediate vertices.
    for (int k = 0; k < V; k++) {
        // Pick all vertices as source one by one
        for (int i = 0; i < V; i++) {
            // Pick all vertices as destination for the
            // above-picked source
            for (int j = 0; j < V; j++) {
                // If vertex k is on the shortest path from
                // i to j, then update the value of
                // dist[i][j]
                if (dist[i][k] != INF && dist[k][j] != INF
                    && dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }

    // Print the shortest distance matrix
    printSolution(dist);
}

int main()
{
    // Define a graph with V vertices
    int graph[V][V] = { { 0, 5, INF, 10 },
                        { INF, 0, 3, INF },
                        { INF, INF, 0, 1 },
                        { INF, INF, INF, 0 } };

    // Perform Floyd-Warshall algorithm to find all pairs
    // shortest paths
    floydWarshall(graph);
    return 0;
}

// C Program for  Johnson's Algorithm
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

// Maximum number of vertices
#define MAX_V 5
#define INF INT_MAX

// Structure to represent an edge
struct Edge {
    int src, dest, weight;
};

// Structure to represent a graph
struct Graph {
    int V, E;
    struct Edge* edge;
};

// Function to create a graph with V vertices and E edges
struct Graph* createGraph(int V, int E)
{
    struct Graph* graph
        = (struct Graph*)malloc(sizeof(struct Graph));
    graph->V = V;
    graph->E = E;
    graph->edge
        = (struct Edge*)malloc(E * sizeof(struct Edge));
    return graph;
}

// Function to perform Bellman-Ford algorithm
void bellmanFord(struct Graph* graph, int src, int dist[])
{
    int V = graph->V;
    int E = graph->E;

    // Initialize distances from src to all other vertices
    // as INFINITE
    for (int i = 0; i < V; i++)
        dist[i] = INF;
    dist[src] = 0;

    // Relax all edges |V| - 1 times
    for (int i = 1; i <= V - 1; i++) {
        for (int j = 0; j < E; j++) {
            int u = graph->edge[j].src;
            int v = graph->edge[j].dest;
            int weight = graph->edge[j].weight;
            if (dist[u] != INF
                && dist[u] + weight < dist[v])
                dist[v] = dist[u] + weight;
        }
    }
}

// Function to find the vertex with the minimum distance
// value
int minDistance(int dist[], int sptSet[], int V)
{
    int min = INF, min_index;
    for (int v = 0; v < V; v++)
        if (sptSet[v] == 0 && dist[v] <= min)
            min = dist[v], min_index = v;
    return min_index;
}

// Function to perform Dijkstra's algorithm
void dijkstra(int graph[MAX_V][MAX_V], int src, int dist[],
              int V)
{
    int sptSet[MAX_V];

    // Initialize distances from src to all other vertices
    // as INFINITE and sptSet[] as false
    for (int i = 0; i < V; i++)
        dist[i] = INF, sptSet[i] = 0;
    dist[src] = 0;

    // Find shortest path for all vertices
    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet, V);
        sptSet[u] = 1;

        for (int v = 0; v < V; v++)
            if (!sptSet[v] && graph[u][v] != INF
                && dist[u] != INF
                && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }
}

// Function to perform Johnson's algorithm
void johnson(struct Graph* graph)
{
    int V = graph->V;

    // Create a new graph with an extra vertex
    struct Graph* g = createGraph(V + 1, graph->E + V);

    // Copy all edges from the original graph to the new
    // graph
    int i;
    for (i = 0; i < graph->E; i++) {
        g->edge[i] = graph->edge[i];
    }

    // Add edges from the new vertex to all other vertices
    // with weight 0
    for (int j = 0; j < V; j++, i++) {
        g->edge[i].src = V;
        g->edge[i].dest = j;
        g->edge[i].weight = 0;
    }

    // Run Bellman-Ford to find shortest paths from the new
    // vertex
    int dist[MAX_V + 1];
    bellmanFord(g, V, dist);

    // Reweight the edges of the original graph
    int reweighted[MAX_V][MAX_V];
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            reweighted[i][j] = (i == j) ? 0 : INF;
        }
    }

    for (int i = 0; i < graph->E; i++) {
        int u = graph->edge[i].src;
        int v = graph->edge[i].dest;
        reweighted[u][v]
            = graph->edge[i].weight + dist[u] - dist[v];
    }

    // Run Dijkstra's algorithm for each vertex
    printf("Shortest distances between every pair of "
           "vertices:\n");
    for (int src = 0; src < V; src++) {
        int shortestDist[MAX_V];
        dijkstra(reweighted, src, shortestDist, V);
        for (int i = 0; i < V; i++) {
            if (shortestDist[i] == INF) {
                printf("%7s", "INF");
            }
            else {
                int distance
                    = shortestDist[i] + dist[i] - dist[src];
                printf("%7d", distance);
            }
        }
        printf("\n");
    }
}

int main()
{
    int V = 4, E = 5;
    struct Graph* graph = createGraph(V, E);

    // Add edges to the graph
    graph->edge[0].src = 0;
    graph->edge[0].dest = 1;
    graph->edge[0].weight = 1;

    graph->edge[1].src = 0;
    graph->edge[1].dest = 2;
    graph->edge[1].weight = 4;

    graph->edge[2].src = 1;
    graph->edge[2].dest = 2;
    graph->edge[2].weight = 2;

    graph->edge[3].src = 1;
    graph->edge[3].dest = 3;
    graph->edge[3].weight = 5;

    graph->edge[4].src = 2;
    graph->edge[4].dest = 3;
    graph->edge[4].weight = 1;

    // Perform Johnson's algorithm to find all pairs
    // shortest paths
    johnson(graph);

    return 0;
}