floyd算法C++代码

以下是Floyd算法的C++代码实现：

Graph.h文件代码：

#ifndef GRAPH_H
#define GRAPH_H

#include <iostream>
#include <vector>

using namespace std;

class Graph {
public:
    Graph(int n);
    ~Graph();
    void addEdge(int u, int v, int w);
    void floyd();
    void print();

private:
    int n;
    vector<vector<int>> dist;
};

#endif // GRAPH_H

Graph.cpp文件代码：

#include "Graph.h"

Graph::Graph(int n) {
    this->n = n;
    dist.resize(n, vector<int>(n, INT_MAX));
    for (int i = 0; i < n; i++) {
        dist[i][i] = 0;
    }
}

Graph::~Graph() {}

void Graph::addEdge(int u, int v, int w) {
    dist[u][v] = w;
}

void Graph::floyd() {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

void Graph::print() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[i][j] == INT_MAX) {
                cout << "INF ";
            } else {
                cout << dist[i][j] << " ";
            }
        }
        cout << endl;
    }
}

main.cpp文件代码：

#include <iostream>
#include "Graph.h"

using namespace std;

int main() {
    int n = 4;
    Graph g(n);

    g.addEdge(0, 1, 5);
    g.addEdge(0, 3, 10);
    g.addEdge(1, 2, 3);
    g.addEdge(2, 3, 1);

    g.floyd();
    g.print();

    return 0;
}

上述代码实现了一个有向图的Floyd算法，其中Graph类中的dist矩阵表示每两个节点之间的距离，如果两个节点之间没有边相连，则距离为INT_MAX。addEdge函数用于添加边，floyd函数用于计算最短路径，print函数用于输出结果。