floyd算法c++实现

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

const int INF = 0x3f3f3f3f; // 定义正无穷

// 图的邻接矩阵表示法，dist[i][j]表示i到j的最短距离
// n为图的节点数，可以根据实际情况修改
int dist[N][N], n;

void floyd() {
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
}

其中，`dist[i][j]`表示节点i到节点j的最短距离，初始化时应该将边权为0的位置设为0，边权为无穷的位置设为正无穷。

时间复杂度为$O(n^3)$。

相关问题

Floyd 算法c++

Floyd 算法（Floyd-Warshall 算法）是一种用于求解图中所有节点对最短路径的算法。下面是用 C++ 实现 Floyd 算法的示例代码：

#include <iostream>
#include <climits>

#define INF INT_MAX

void floydWarshall(int graph[][4], int V) {
    int dist[V][V];

    // 初始化距离矩阵
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            dist[i][j] = graph[i][j];
        }
    }

    // 通过中间节点 k 逐步更新最短路径
    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                // 如果经过节点 k 的路径比直接路径更短，则更新距离
                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];
                }
            }
        }
    }

    // 打印最短路径矩阵
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (dist[i][j] == INF) {
                std::cout << "INF ";
            } else {
                std::cout << dist[i][j] << " ";
            }
        }
        std::cout << std::endl;
    }
}

int main() {
    int graph[4][4] = {{0, 5, INF, 10},
                       {INF, 0, 3, INF},
                       {INF, INF, 0, 1},
                       {INF, INF, INF, 0}};

    floydWarshall(graph, 4);

    return 0;
}

这是一个简单的实现示例，通过传入一个邻接矩阵来计算所有节点对的最短路径。在这个示例中，图中共有4个节点，用一个4x4的邻接矩阵表示。其中，INF 表示两个节点之间没有直接连接。程序输出的结果是一个4x4的矩阵，表示任意两个节点之间的最短路径长度。

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函数用于输出结果。