图的遍历

广度优先搜索(BFS)

将当前访问结点所连接的结点依次遍历，由近到远，类似于树的层序遍历

#include <queue>
#include <vector>

using namespace std;
vector<pair<int, int>> dict{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
/**
 * @brief 广度优先搜索
 * @param grid: 邻接矩阵存储的图
 * @param visited: 标记各结点是否被访问过
 * @param x: 访问的结点行下标
 * @param y: 访问的结点列下标
 */
void bfs(vector<vector<int>> &grid, vector<vector<bool>> &visited, int x, int y)
{
    int m = grid.size();
    int n = grid[0].size();

    queue<pair<int, int>> que;
    que.push({x, y});     // 将当前访问的结点加入队列
    visited[x][y] = true; // 标记为已访问

    while (!que.empty())
    {
        pair<int, int> cur = que.front(); // 取队首元素
        que.pop();                        // 出队

        // 上下左右依次访问
        for (auto dir : dict)
        {
            int nextX = cur.first + dir.first;
            int nextY = cur.second + dir.second;
            // 是否越界
            if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n)
            {
                // 当前结点未被访问过
                if (!visited[nextX][nextY])
                {
                    que.push({nextX, nextY});     // 入队
                    visited[nextX][nextY] = true; // 标记访问
                }
            }
        }
    }
}

时间复杂度：邻接表$O(V+E)$，每个顶点和边各访问一次；邻接矩阵$O(V^2)$，遍历矩阵

空间复杂度：最坏情况$O(V)$，由队列和访问数组决定

深度优先搜索(DFS)

沿着当前访问结点所连接的其中一个结点一路访问到底

#include <iostream>
#include <vector>

using namespace std;

vector<pair<int, int>> dict{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
/**
 * @brief 深度优先搜索
 * @param grid 二维网格
 * @param visited 访问标记数组
 * @param x 当前行
 * @param y 当前列
 */
void dfs(vector<vector>& grid, vector<bool>& visited, int x, int y) {
    if(!visited[x][y] || grid[x][y])
    {
        return;
    }
    visited[x][y] = true;
    for(auto dir : dict)
    {
        int nextX = x + dir.first;
        int nextY = y + dir.second;
        if(nextX >= 0 && nextX < grid.size() && nextY >= 0 && nextY < grid[0].size())
        {
            dfs(grid, visited, nextX, nextY);
        }
    }
}

时间复杂度：邻接表$O(V+E)$，每个顶点和边各访问一次；邻接矩阵$O(V^2)$，遍历矩阵

空间复杂度：最坏情况$O(V)$，由队列和访问数组决定

并查集

见数据结构：并查集

最小生成树

生成所有结点的最小连通子图，以最小的成本(权值和)保证图中所有结点都是连通的，n个结点需要n-1条边

prim算法

从结点的角度采用贪心策略，每次选取距离已构造的生成树最近的结点加入到生成树中

算法步骤：

1. 选择距离生成树最近的结点
2. 将该结点加入生成树
3. 更新非树结点到生成树的距离（更新minDist数组）

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int main(int argc, char const *argv[])
{
    // 输入
    int v, e;
    int x, y, k;
    cin >> v >> e;
    vector<vector<int>> graph(v + 1, vector<int>(v + 1, INT_MAX));
    while (e--)
    {
        cin >> x >> y >> k;
        graph[x][y] = k;
        graph[y][x] = k;
    }

    // prim算法
    vector<int> minDist(v + 1, INT_MAX); // 各节点到最小生成树的最小距离
    vector<bool> isInTree(v + 1, false); // 是否在最小生成树中

    // 循环v-1次，建立v-1条边
    for (int i = 1; i < v; i++)
    {
        // 1、选距离生成树最近的节点
        int cur = -1;
        int minVal = INT_MAX;
        for (int j = 1; j <= v; j++)
        {
            // (1)当前节点不在树中
            // (2)当前节点到树的距离小于当前最小值
            if (!isInTree[j] && minDist[j] < minVal)
            {
                cur = j;
                minVal = minDist[j];
            }
        }
        // 2、将当前节点加入树中
        isInTree[cur] = true;

        // 3、更新其他节点到树的距离
        for (int j = 1; j <= v; j++)
        {
            // (1)当前节点不在树中
            // (2)当前节点到树的距离大于当前节点到树的距离
            if (!isInTree[j])
            {
                minDist[j] = min(minDist[j], graph[cur][j]);
            }
        }
    }

    // 输出
    int res = 0;
    for (int i = 2; i <= v; i++)
    {
        res += minDist[i];
    }
    cout << res << endl;

    return 0;
}

时间复杂度：$O(n^2)$

空间复杂度：$O(n)$

Kruskal算法

从边的角度采用贪心策略，每次选取非生成树节点之间的最小权值边，将边上的节点加入生成树中

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

struct Edge
{
    int from; // 起点
    int to;   // 终点
    int val;  // 权重
};

int n = INT_MAX;           // 节点数
vector<int> father(n, -1); // 记录每个节点的父节点

// 并查集初始化
void init()
{
    for (int i = 0; i < n; i++)
    {
        father[i] = i;
    }
}

// 查找父节点
int find(int u)
{
    return father[u] == u ? u : find(father[u]);
}

// 判断u和v是否在同一集合中
bool isSame(int u, int v)
{
    u = find(u);
    v = find(v);
    return u == v;
}

// 合并u和v所在的集合 u<-v
void join(int u, int v)
{
    u = find(u);
    v = find(v);
    if (u != v)
    {
        father[v] = u; // 将u的父节点设置为v
    }
}

int main(int argc, char const *argv[])
{
    // 输入
    int v, e;
    int x, y, k;
    cin >> v >> e;
    vector<Edge> edges;
    while (e--)
    {
        cin >> x >> y >> k;
        edges.push_back({x, y, k});
    }

    // Kruskal算法
    // 根据边的权值排序
    sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b)
         {
             return a.val < b.val; // 按照权值升序排序
         });

    init(); // 初始化并查集
    int res = 0;

    for (Edge edge : edges)
    {
        // 查找边上两节点的祖先
        int from = find(edge.from);
        int to = find(edge.to);

        // 两节点祖先不同，则合并集合
        if (from != to)
        {
            res += edge.val; // 计算最小生成树的权值和
            join(from, to);  // 合并集合
        }
    }

    // 输出
    cout << res << endl;

    return 0;
}

时间复杂度：$O(nlogn)$ = $O(nlogn)$（快排） + $O(logn)$（并查集）

空间复杂度：$O(n)$

拓扑排序

将有向图转成线性排序，或用于判断有向无环图

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;

int main(int argc, char const *argv[])
{
    int m, n, s, t;
    cin >> n >> m;
    vector<int> inDegree(n + 1, 0); // 记录每个文件的入度

    unordered_map<int, vector<int>> umap; // 记录结点之间的依赖关系，结点->结点
    vector<int> res;                      // 记录拓扑排序的结果

    for (int i = 0; i < m; i++)
    {
        cin >> s >> t;
        umap[s].push_back(t); // s->t
        inDegree[t]++;        // t的入度加1
    }
    queue<int> que; // 队列
    for (int i = 1; i <= n; i++)
    {
        if (inDegree[i] == 0) // 如果入度为0，说明没有依赖关系
        {
            que.push(i); // 入队
        }
    }
    while (!que.empty())
    {
        int cur = que.front(); // 取出队头元素
        que.pop();             // 出队
        res.push_back(cur);    // 加入结果中
        for (int i = 0; i < umap[cur].size(); i++)
        {
            inDegree[umap[cur][i]]--;        // 该结点的入度减1
            if (inDegree[umap[cur][i]] == 0) // 入度为0
            {
                que.push(umap[cur][i]); // 入队
            }
        }
    }
    if (res.size() == n)
    {
        for (int i = 0; i < res.size(); i++)
        {
            cout << res[i] << " "; // 输出结果
        }
    }
    else
    {
        cout << "0"; // 有环，输出0
    }
    return 0;
}

时间复杂度：$O(V+E)$

空间复杂度：$O(V)$

最短路问题

Dijkstra算法

在非负权图中求起点到其他结点的最短路径算法

算法步骤：

1. 从未被访问的结点中选一个距离起点最近的
2. 标记该节点为已访问
3. 更新各结点到起点的距离（更新minDist数组）

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int main(int argc, char const *argv[])
{
    int m, n, p1, p2, val;
    cin >> n >> m;

    // 邻接矩阵存储
    vector<vector<int>> grid(n + 1, vector<int>(n + 1, INT_MAX));
    for (int i = 0; i < m; i++)
    {
        cin >> p1 >> p2 >> val;
        grid[p1][p2] = val;
    }

    int start = 1; // 起点
    int end = n;   // 终点

    // Dijkstra算法
    vector<int> minDist(n + 1, INT_MAX); // 存储最短路径
    vector<bool> visited(n + 1, false);  // 标记节点是否已访问

    minDist[start] = 0; // 起点到起点的距离为 0

    // 遍历所有结点
    for (int i = 1; i <= n; i++)
    {
        int minVal = INT_MAX;
        int cur = 1;

        // 1、选距离原点且未被访问的结点
        for (int v = 1; v <= n; v++)
        {
            if (!visited[v] && minDist[v] < minVal)
            {
                minVal = minDist[v];
                cur = v;
            }
        }

        // 2、标记该结点为已访问
        visited[cur] = true;

        // 3、更新minDist
        for (int v = 1; v <= n; v++)
        {
            if (!visited[v] && grid[cur][v] != INT_MAX)
            {
                minDist[v] = min(minDist[v], minDist[cur] + grid[cur][v]);
            }
        }
    }

    // 输出
    if (minDist[end] == INT_MAX)
    {
        cout << -1 << endl; // 无法到达终点
    }
    else
    {
        cout << minDist[end] << endl; // 输出最短路径
    }
    return 0;
}

时间复杂度：$O(n^2)$，适合应用于稠密图

空间复杂度：$O(n^2)$

Dijkstra与prim的区别

Dijkstra求的是非访问节点到起点的最小距离，prim求的是非访问结点到最小生成树的最小距离，核心区别如下：

// 更新minDist
for (int v = 1; v <= n; v++)
{
    if (!visited[v] && grid[cur][v] != INT_MAX)
    {
        minDist[v] = min(minDist[v], minDist[cur] + grid[cur][v]);
    }
}

// 更新minDist
for (int v = 1; v <= n; v++)
{
    if (!isInTree[v])
    {
        minDist[v] = min(minDist[v], grid[cur][v]);
    }
}

在Dijkstra中，非访问结点到起点的最小距离 = 起点到当前最近结点距离minDist[cur] + 当前结点到非访问结点距离grid[cur][v]

在prim中，非访问结点到最小生成树的最小距离 = 当前结点到非访问距离结点grid[cur][v]

堆优化

使用邻接表存储各点所连接的边，使用**优先队列（小根堆）**使各边按权值排序，选取非访问节点到起点的最小距离

#include <iostream>
#include <vector>
#include <climits>
#include <queue>
#include <list>

using namespace std;

**class mycomparison
{
public:
    bool operator()(const pair<int, int> &lhs, const pair<int, int> &rhs)
    {
        return lhs.second > rhs.second; // 这里是大于号，表示小根堆
    }
};

struct Edge
{
    int to;
    int val;
};**

int main(int argc, char const *argv[])
{
    int m, n, p1, p2, val;
    cin >> n >> m;

    // 邻接表存储
    vector<list<Edge>> grid(n + 1);
    for (int i = 0; i < m; i++)
    {
        cin >> p1 >> p2 >> val;
        grid[p1].push_back({p2, val});
    }

    int start = 1; // 起点
    int end = n;   // 终点

    // Dijkstra算法_堆优化
    vector<int> minDist(n + 1, INT_MAX); // 存储最短路径
    vector<bool> visited(n + 1, false);  // 标记节点是否已访问

    // 优先队列存放各边
    **priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pq;**

    minDist[start] = 0;  // 起点到起点的距离为 0
    pq.push({start, 0}); // 将起点加入优先队列

    while (!pq.empty())
    {
        // 1、选距离原点且未被访问的结点
        **pair<int, int> cur = pq.top();

        pq.pop();

        if (visited[cur.first])
        {
            continue; // 如果该结点已访问，则跳过
        }

        // 2、标记该结点为已访问
        visited[cur.first] = true;

        // 3、更新minDist
        for (Edge edge : grid[cur.first])
        {
            int to = edge.to;
            int val = edge.val;
            if (!visited[to] && minDist[cur.first] + val < minDist[to])
            {
                minDist[to] = minDist[cur.first] + val; // 更新最短路径
                pq.push({to, minDist[to]});             // 将更新后的结点加入优先队列
            }
        }**
    }

    // 输出
    if (minDist[end] == INT_MAX)
    {
        cout << -1 << endl; // 无法到达终点
    }
    else
    {
        cout << minDist[end] << endl; // 输出最短路径
    }
    return 0;
}

时间复杂度：$O(ElogE)$，E为边的数量，适合应用于稀疏图

空间复杂度：$O(N + E)$，N为节点数量

Bellman_ford算法

适用于带负权值的单源最短路问题，其核心思想是对所有边松弛n-1次

松弛：通过A→B边获得更短的起点到达B节点的路径，则更新。i次松弛可以获得起点经过i条边到达某个节点的最短距离，从起点到节点i最多i-1条边相连，则松弛i-1次可获得起点到节点i的最短路径

#include <iostream>
#include <vector>
#include <climits>
#include <list>

using namespace std;

struct Edge
{
    int from;
    int to;
    int val;
};

int main(int argc, char const *argv[])
{
    int m, n, p1, p2, val;
    cin >> n >> m;

    // 邻接表存储
    vector<Edge> edges;
    for (int i = 0; i < m; i++)
    {
        cin >> p1 >> p2 >> val;
        edges.push_back({p1, p2, val});
    }

    int start = 1; // 起点
    int end = n;   // 终点

    // Bellman_ford 算法
    vector<int> minDist(n + 1, INT_MAX); // 存储最短路径

    minDist[start] = 0; // 起点到起点的距离为 0

    // n个节点，做n-1次松弛操作
    for (int i = 1; i < n; i++)
    {
        for (Edge edge : edges)
        {
            int from = edge.from;
            int to = edge.to;
            int val = edge.val;

            // 松弛操作
            if (minDist[from] != INT_MAX && minDist[from] + val < minDist[to])
            {
                minDist[to] = minDist[from] + val; // 更新最短路径
            }
        }
    }

    // 输出
    if (minDist[end] == INT_MAX)
    {
        cout << "unconnected" << endl; // 无法到达终点
    }
    else
    {
        cout << minDist[end] << endl; // 输出最短路径
    }
    return 0;
}

时间复杂度：$O(N*E)$，N为节点数量，E为边的数量

空间复杂度：$O(N)$，即minDist数组开辟的空间

SPFA算法(Bellman_ford队列优化)

由于仅当minDist[i] != INT_MAX 时，松弛才有意义，所以使用队列存储最新更新过的节点，针对这些节点所连接的边进行松弛

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <list>

using namespace std;

struct Edge
{
    int to;
    int val;
};

int main(int argc, char const *argv[])
{
    int m, n, p1, p2, val;
    cin >> n >> m;

    // 邻接表存储
    vector<list<Edge>> edges(n + 1);
    vector<bool> isInQueue(n + 1, false); // 记录节点是否在队列中
    for (int i = 0; i < m; i++)
    {
        cin >> p1 >> p2 >> val;
        edges[p1].push_back({p2, val});
    }

    int start = 1; // 起点
    int end = n;   // 终点

    // Bellman_ford 算法
    vector<int> minDist(n + 1, INT_MAX); // 存储最短路径
    minDist[start] = 0;                  // 起点到起点的距离为 0

    queue<int> que;
    que.push(start); // 将起点加入队列

    while (!que.empty())
    {
        int from = que.front();
        que.pop();
        isInQueue[from] = false; // 标记当前节点不在队列中
        for (Edge edge : edges[from])
        {
            int to = edge.to;
            int val = edge.val;

            // 松弛操作
            if (minDist[from] + val < minDist[to])
            {
                minDist[to] = minDist[from] + val; // 更新最短路径
                if (isInQueue[to] == false)        // 如果节点不在队列中
                {
                    que.push(to);         // 将节点加入队列，每个节点会在这里多次入队
                    isInQueue[to] = true; // 标记节点在队列中
                }
            }
        }
    }

    // 输出
    if (minDist[end] == INT_MAX)
    {
        cout << "unconnected" << endl; // 无法到达终点
    }
    else
    {
        cout << minDist[end] << endl; // 输出最短路径
    }
    return 0;
}

时间复杂度：$O(KN)$，最坏情况$O(NE)$(稠密图)

空间复杂度：$O(N)$

Floyd算法

多源最短路算法，对边的权值没有正负要求，适用于稠密图且源点较多的情况，核心思想是动态规划

使用grid数组存储图中各节点的最短距离，同时也是dp数组，有grid[i][j][k] = m，表示节点i到节点j经过集合[1…k]中的某个节点的最短距离为m。

递推公式：

1. 节点i到节点j的最短路径经过节点k grid[i][j][k] = grid[i][k][k - 1] + grid[k][j][k - 1]
2. 节点i到节点j的最短路径不经过节点k grid[i][j][k] = grid[i][j][k - 1]

综上，grid[i][j][k] = min(grid[i][j][k - 1], grid[i][k][k - 1] + grid[k][j][k - 1])

确定遍历顺序：由于当前需要求得的最短路dp[i][j][k]依赖于k - 1时的状态，所以每次循环需要保证当前k - 1轮的状态全部算完以供k轮使用，所以遍历顺序k一定要在最外层

#include <iostream>
#include <vector>
#include <list>

using namespace std;

int main(int argc, char const *argv[])
{
    int m, n, p1, p2, val;
    cin >> n >> m;

    // 三维dp数组
    // grid[i][j][k]表示从i到j经过[1...k]中某个点的最短路径
    vector<vector<vector<int>>> grid(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, INT_MAX)));
    for (int i = 0; i < m; i++)
    {
        cin >> p1 >> p2 >> val; // 输入边的起点、终点和权值
        grid[p1][p2][0] = val;  // 初始化边的权值
        grid[p2][p1][0] = val;  // 无向图，双向边
    }

    // Floyd算法
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                grid[i][j][k] = min(grid[i][j][k - 1], grid[i][k][k - 1] + grid[k][j][k - 1]);
            }
        }
    }

    // 输出
    int z, start, end;
    cin >> z;
    while (z--)
    {
        cin >> start >> end;
        if (grid[start][end][n] == INT_MAX)
        {
            cout << -1 << endl; // 如果没有路径
        }
        else
        {
            cout << grid[start][end][n] << endl; // 输出最短路径
        }
    }

    return 0;
}

时间复杂度：$O(N^3)$

空间复杂度：$O(N^3)$

空间优化

由grid[i][j][k]的递推公式可知第k轮的结果仅依赖于第k - 1轮的结果，则递推公式可优化为：

grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j]

#include <iostream>
#include <vector>
#include <list>

using namespace std;

int main(int argc, char const *argv[])
{
    int m, n, p1, p2, val;
    cin >> n >> m;

    // 二维dp数组
    // grid[i][j]表示从i到j经过[1...k]中某个点的最短路径
    vector<vector<int>> grid(n + 1, vector<int>(n + 1, INT_MAX));
    for (int i = 0; i < m; i++)
    {
        cin >> p1 >> p2 >> val; // 输入边的起点、终点和权值
        grid[p1][p2] = val;     // 初始化边的权值
        grid[p2][p1] = val;     // 无向图，双向边
    }

    // Floyd算法
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j]);
            }
        }
    }

    // 输出
    int z, start, end;
    cin >> z;
    while (z--)
    {
        cin >> start >> end;
        if (grid[start][end] == INT_MAX)
        {
            cout << -1 << endl; // 如果没有路径
        }
        else
        {
            cout << grid[start][end] << endl; // 输出最短路径
        }
    }

    return 0;
}

时间复杂度：$O(N^3)$

空间复杂度：$O(N^2)$

A*算法

A*算法是一种广泛应用于路径搜索和图遍历算法，在图形平面上寻找从起点到终点的最优路径，其结合了Dijkstra算法的完备性和贪心最佳优先搜索的高效性，通过启发式函数来指导搜索方向

核心原理

通过评估函数$f(n)=g(n)+h(n)$来决定搜索顺序：

• $g(n)$：从起点到节点n的实际代价
• $h(n)$：从节点n到终点的估计代价（启发式函数）
• $f(n)$：通过节点n的总估计代价

h(n)通常为节点n到终点的距离，主要有：

• 曼哈顿距离：$d=abs(x_1-x_2)+abs(y_1-y_2)$
• 欧氏距离（欧拉距离）：$d=sqrt((x_1-x_2)^2+(y_1-y_2)^2)$
• 切比雪夫距离：$d=max(abs(x_1-x_2),abs(y_1-y_2))$

代码

#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int moves[1001][1001];
vector<pair<int, int>> dict{{-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}};
int b1, b2;

struct Knight
{
    int x, y;
    int g, h, f;
    bool operator<(const Knight &other) const
    {
        return other.f > f; // 小堆顶
    }
};

priority_queue<Knight> que;

int Heuristic(const Knight &k)
{
    // 不开根号提升精度
    return (k.x - b1) * (k.x - b1) + (k.y - b2) * (k.y - b2);
}

void astar(const Knight &k)
{
    Knight cur, next;
    que.push(k);
    while (!que.empty())
    {
        cur = que.top();
        que.pop();
        if (cur.x == b1 && cur.y == b2)
        {
            break;
            return;
        }
        for (auto dir : dict)
        {
            next.x = cur.x + dir.first;
            next.y = cur.y + dir.second;
            if (next.x < 1 || next.x > 1000 || next.y < 1 || next.y > 1000)
            {
                continue;
            }
            if (!moves[next.x][next.y])
            {
                moves[next.x][next.y] = moves[cur.x][cur.y] + 1;

                // 计算f值
                next.g = cur.g + 5;
                next.h = Heuristic(next);
                next.f = next.g + next.h;
                que.push(next);
            }
        }
    }
}

int main(int argc, char const *argv[])
{
    int n, a1, a2;
    cin >> n;
    while (n--)
    {
        cin >> a1 >> a2 >> b1 >> b2;
        memset(moves, 0, sizeof(moves));
        Knight start;
        start.x = a1;
        start.y = a2;
        start.g = 0;
        start.h = Heuristic(start);
        start.f = start.g + start.h;
        astar(start);
        while (!que.empty())
        {
            que.pop();
        }
        cout << moves[b1][b2] << endl;
    }

    return 0;
}

时间复杂度：时间复杂度取决于启发式函数，最坏情况下$O(N^2)$，最佳情况$O(dlogd)$，d为起点到终点的深度，一般情况下$O(NlogN)$

空间复杂度：$O(b^d)$，b为节点间连接数，d为起点到终点的深度

最短路问题总结

	适用图的大小	边权值能否为负	检测负权回路	有限节点最短路径	源点数	时间复杂度
Dijkstra	稠密图	否	否	否	单源	$O(N^2)$，N为节点数量
Dijkstra堆优化	稠密图	否	否	否	单源	$O(ElogE)$，E为边数量
Bellman_Ford	稠密图	是	是	是	单源	$O(N*E)$，N为节点数量，E为边数量
SPFA(Bellman_Ford队列优化)	稠密图	是	是	是	单源	$O(K*N)$，K为不定值，取决于图的稠密度
Floyd	稠密图	是	是	否	多源	$O(N^3)$，N为节点数量

注：A*算法属于启发式搜索，其时间复杂度由启发式函数决定