建立无向图然后用dijjstra算法算最短路径优缺点

Dijkstra算法是一种用于解决单源最短路径问题的经典算法，可以应用于有向图和无向图。下面是Dijkstra算法的优缺点：

优点：
1. 算法保证能够找到最短路径。对于没有负权边的图，Dijkstra算法是一种可靠的解决方案。
2. 算法适用于稠密图和稀疏图，效率较高。
3. 在负权边的情况下，Dijkstra算法可以处理一部分问题，例如当图中不存在负权环时，仍然能够得到正确的结果。

缺点：
1. Dijkstra算法对于带有负权边的图不适用，因为它依赖于“贪心选择最短路径”的策略，而负权边可能导致无限循环。
2. 算法的时间复杂度为O(V^2)，其中V为图中顶点的数量。在大规模图中，效率可能较低。
3. 算法不能处理存在负权环的情况，因为在这种情况下，没有明确的最短路径。

总结起来，Dijkstra算法是一种简单而有效的算法，适用于解决无向图中单源最短路径问题。然而，在处理带有负权边或存在负权环的图时，就需要使用其他算法来解决。

相关问题

无向图最短路径算法 c

最短路径问题是图论研究中的一个经典算法问题，旨在寻找图中两个结点之间的最短路径。其中一个常用的算法是Dijkstra算法（迪杰斯特拉算法）。该算法的步骤如下：
1. 初始化距离数组D，将起始结点的距离设为0。
2. 创建一个集合S，用来存放已经确定最短路径的结点。
3. 循环n-1次，每次选取一个距离最短且不在集合S中的结点vk，将其加入集合S。
4. 根据条件更新从起始结点到集合S中的所有结点的最短路径长度，即如果存在结点vi，满足D[k] + G.arcs[k][i] < D[i]，则更新D[i] = D[k] + G.arcs[k][i]，同时更新结点vi的前驱为vk。

对于给定的无向图最短路径问题，一种常见的解决方法是将无向图转换为有向图，在有向图上应用Dijkstra算法求解最短路径。转换方法可以是将每条无向边(u, v)转化为有向边(u, v)和(v, u)。然后按照上述步骤执行Dijkstra算法即可得到最短路径。

floyd算法求无向图的最短路径并输出最短路径及其长度c语言

以下是C语言实现Floyd算法求解无向图最短路径及其长度的示例代码：

#include <stdio.h>
#define INF 0x3f3f3f3f // 无穷大

int main()
{
    int n, m;
    scanf("%d %d", &n, &m); // 输入结点数和边数

    int dist[n+1][n+1]; // 存储结点间距离
    memset(dist, INF, sizeof(dist)); // 初始化为无穷大
    for(int i = 1; i <= n; i++)
        dist[i][i] = 0; // 自身到自身的距离为0

    int u, v, w;
    for(int i = 1; i <= m; i++)
    {
        scanf("%d %d %d", &u, &v, &w); // 输入边的起点、终点和权值
        dist[u][v] = w;
        dist[v][u] = w; // 无向图需要双向存储
    }

    // Floyd算法求解最短路径
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if(dist[i][j] > dist[i][k] + dist[k][j])
                    dist[i][j] = dist[i][k] + dist[k][j];

    // 输出最短路径及其长度
    for(int i = 1; i <= n; i++)
        for(int j = i+1; j <= n; j++)
            printf("%d 到 %d 的最短路径为 %d，路径长度为 %d\n", i, j, j, dist[i][j]);

    return 0;
}

在输入时，需要按照以下格式输入：

- 第一行为结点数n和边数m，用空格分隔；
- 接下来m行每行为一条边的起点u、终点v和权值w，用空格分隔。

例如，以下是一个包含5个结点和7条边的无向图的输入示例：

5 7
1 2 2
1 3 4
2 3 1
2 4 7
3 4 3
3 5 6
4 5 5

输出结果如下：

1 到 2 的最短路径为 2，路径长度为 2
1 到 3 的最短路径为 3，路径长度为 4
1 到 4 的最短路径为 3，路径长度为 10
1 到 5 的最短路径为 4，路径长度为 9
2 到 3 的最短路径为 3，路径长度为 1
2 到 4 的最短路径为 4，路径长度为 8
2 到 5 的最短路径为 3，路径长度为 7
3 到 4 的最短路径为 3，路径长度为 3
3 到 5 的最短路径为 3，路径长度为 6
4 到 5 的最短路径为 5，路径长度为 5