C/Visual C - codigo C/C++ dijkstra y floyd

#include <iostream>

#include <vector>

#include <queue>

#include <climits>

using namespace std;

#define INF INT_MAX

// Estructura para representar una arista

struct Edge {

    int destination;

    int weight;

};

// Función para implementar el algoritmo de Dijkstra

void Dijkstra(vector<vector<Edge>>& graph, int source) {

    int n = graph.size();

    vector<int> distance(n, INF);

    vector<bool> visited(n, false);

    distance[source] = 0;

    // Cola de prioridad para almacenar los nodos a visitar

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    pq.push({0, source});

    while (!pq.empty()) {

        int u = pq.top().second;

        pq.pop();

        if (visited[u]) {

            continue;

        }

        visited[u] = true;

        for (const auto& edge : graph[u]) {

            int v = edge.destination;

            int weight = edge.weight;

            if (distance[u] + weight < distance[v]) {

                distance[v] = distance[u] + weight;

                pq.push({distance[v], v});

            }

        }

    }

    // Imprimir las distancias mínimas desde el origen a todos los nodos

    cout << "Distancias mínimas desde el nodo fuente " << source << ":\n";

    for (int i = 0; i < n; i++) {

        cout << "Nodo " << i << ": " << distance[i] << "\n";

    }

}

int main() {

    int n, m;

    cout << "Ingrese el número de nodos: ";

    cin >> n;

    cout << "Ingrese el número de aristas: ";

    cin >> m;

    vector<vector<Edge>> graph(n);

    cout << "Ingrese las aristas en el formato 'nodo_origen nodo_destino peso':\n";

    for (int i = 0; i < m; i++) {

        int u, v, weight;

        cin >> u >> v >> weight;

        graph[u].push_back({v, weight});

    }

    int source;

    cout << "Ingrese el nodo fuente: ";

    cin >> source;

    Dijkstra(graph, source);

    return 0;

}

#include <iostream>

#include <vector>

#include <climits>

using namespace std;

#define INF INT_MAX

// Función para implementar el algoritmo de Floyd

void Floyd(vector<vector<int>>& graph) {

    int n = graph.size();

    // Inicializar la matriz de distancias mínimas

    vector<vector<int>> distance(n, vector<int>(n, INF));

    // Inicializar la matriz de caminos intermedios

    vector<vector<int>> next(n, vector<int>(n, -1));

    // Inicializar las distancias mínimas y los caminos intermedios

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < n; j++) {

            distance[i][j] = graph[i][j];

            if (graph[i][j] != INF && i != j) {

                next[i][j] = i;

            }

        }

    }

    // Calcular las distancias mínimas y los caminos intermedios

    for (int k = 0; k < n; k++) {

        for (int i = 0; i < n; i++) {

            for (int j = 0; j < n; j++) {

                if (distance[i][k] != INF && distance[k][j] != INF && distance[i][k] + distance[k][j] < distance[i][j]) {

                    distance[i][j] = distance[i][k] + distance[k][j];

                    next[i][j] = next[k][j];

                }

            }

        }

    }

    // Imprimir las distancias mínimas y los caminos intermedios

    cout << "Matriz de distancias mínimas:\n";

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < n; j++) {

            if (distance[i][j] == INF) {

                cout << "INF ";

            } else {

                cout << distance[i][j] << " ";

            }

        }

        cout << "\n";

    }

    cout << "Matriz de caminos intermedios:\n";

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < n; j++) {

            if (next[i][j] == -1) {

                cout << "- ";

            } else {

                cout << next[i][j] << " ";

            }

        }

        cout << "\n";

    }

}

int main() {

    int n;

    cout << "Ingrese el número de nodos: ";

    cin >> n;

    vector<vector<int>> graph(n, vector<int>(n));

    cout << "Ingrese la matriz de adyacencia del grafo (utilice INF para representar la ausencia de aristas):\n";

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < n; j++) {

            cin >> graph[i][j];

        }

    }

    Floyd(graph);

    return 0;

}