对于有权重的矩阵的有向图求解完全最短路径

求解有权重的矩阵的有向图的完全最短路径可以使用Floyd算法。Floyd算法采用动态规划的思想，通过计算出所有节点之间的最短路径长度，逐步求解出完全最短路径。具体实现过程如下：

1. 初始化：将所有节点之间的距离赋值给二维数组dist。

2. 通过中转点k，更新节点i到节点j的最短路径长度：dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])。

3. 重复步骤2，直到所有节点之间的最短路径长度计算完成。

4. 最终得到的二维数组dist中的值即为所有节点之间的完全最短路径长度。

需要注意的是，当图中存在负权边时，Floyd算法可能会得到错误的结果。此时可以使用Bellman-Ford算法或Dijkstra算法等其他算法来求解最短路径。

相关问题

c语言编程有向图的最短路径

要实现有向图的最短路径算法，可以使用 Dijkstra 算法或者 Bellman-Ford 算法。下面分别介绍这两种算法的实现方法。

1. Dijkstra 算法

Dijkstra 算法是一种贪心算法，用于求解带权有向图中单源最短路径问题。算法的基本思路是，维护一个集合 S 和一个距离数组 dist，初始时集合 S 中只包含源点，dist 中除源点外所有节点的距离都为无穷大。每次从 dist 中选取距离最小的节点 u，并将 u 加入集合 S 中，然后更新 u 的邻居节点的距离。重复执行这个过程，直到所有节点都被加入集合 S 中。

以下是 Dijkstra 算法的 C 语言实现代码：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAXN 1000
#define INF INT_MAX

int n, m;  // n 表示节点数，m 表示边数
int g[MAXN][MAXN];  // 存储图的邻接矩阵
int dist[MAXN];  // 存储距离数组
int visited[MAXN];  // 记录节点是否被访问过

void dijkstra(int s) {
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
        visited[i] = 0;
    }
    dist[s] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
                u = j;
            }
        }
        visited[u] = 1;
        for (int v = 0; v < n; v++) {
            if (!visited[v] && g[u][v] != INF && dist[u] + g[u][v] < dist[v]) {
                dist[v] = dist[u] + g[u][v];
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            g[i][j] = INF;
        }
    }
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        g[u][v] = w;  // 存储边权
    }
    int s;
    scanf("%d", &s);  // 输入源点
    dijkstra(s);
    for (int i = 0; i < n; i++) {
        if (dist[i] == INF) {
            printf("INF ");
        } else {
            printf("%d ", dist[i]);
        }
    }
    printf("\n");
    return 0;
}

2. Bellman-Ford 算法

Bellman-Ford 算法是一种动态规划算法，用于求解带权有向图中单源最短路径问题。算法的基本思路是，从源点开始进行 n-1 轮松弛操作，每轮松弛操作将所有边进行一次松弛，即尝试通过一条边缩短到达一个节点的距离。若在第 n 轮松弛操作后仍然存在可松弛的边，则说明图中存在负环，即存在一个环，使得沿着这个环的方向遍历会使得距离越来越小。因此，Bellman-Ford 算法也可以用于检测负环。

以下是 Bellman-Ford 算法的 C 语言实现代码：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAXN 1000
#define INF INT_MAX

int n, m;  // n 表示节点数，m 表示边数
int u[MAXN], v[MAXN], w[MAXN];  // 存储边的起点、终点和权重
int dist[MAXN];  // 存储距离数组

void bellman_ford(int s) {
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
    }
    dist[s] = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < m; j++) {
            if (dist[u[j]] != INF && dist[u[j]] + w[j] < dist[v[j]]) {
                dist[v[j]] = dist[u[j]] + w[j];
            }
        }
    }
    for (int j = 0; j < m; j++) {
        if (dist[u[j]] != INF && dist[u[j]] + w[j] < dist[v[j]]) {
            printf("Graph contains negative-weight cycle\n");
            return;
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &u[i], &v[i], &w[i]);
    }
    int s;
    scanf("%d", &s);  // 输入源点
    bellman_ford(s);
    for (int i = 0; i < n; i++) {
        if (dist[i] == INF) {
            printf("INF ");
        } else {
            printf("%d ", dist[i]);
        }
    }
    printf("\n");
    return 0;
}

迪杰特斯拉算法c++最短路径有向图

迪杰斯特拉（Dijkstra）算法是一种用于求解带权有向图中单源最短路径的算法。下面是一个使用C语言实现的简单示例：

#include <stdio.h>
#include <limits.h>

#define V 9  // 图的顶点数

// 找到距离数组dist[]中最小值的顶点索引
int minDistance(int dist[], bool visited[])
{
    int min = INT_MAX, minIndex;

    for (int v = 0; v < V; v++)
    {
        if (visited[v] == false && dist[v] <= min)
        {
            min = dist[v];
            minIndex = v;
        }
    }

    return minIndex;
}

// 打印最短路径结果
void printSolution(int dist[])
{
    printf("顶点\t距离\n");
    for (int i = 0; i < V; i++)
    {
        printf("%d\t%d\n", i, dist[i]);
    }
}

void dijkstra(int graph[V][V], int src)
{
    int dist[V];     // 存储最短路径
    bool visited[V]; // 标记顶点是否被访问过

    // 初始化距离数组和访问标记数组
    for (int i = 0; i < V; i++)
    {
        dist[i] = INT_MAX;
        visited[i] = false;
    }

    dist[src] = 0; // 源顶点到自身的距离为0

    for (int count = 0; count < V - 1; count++)
    {
        int u = minDistance(dist, visited);
        visited[u] = true;

        for (int v = 0; v < V; v++)
        {
            // 更新距离数组
            if (!visited[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])
            {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    printSolution(dist);
}

int main()
{
    int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
                       {4, 0, 8, 0, 0, 0, 0, 11, 0},
                       {0, 8, 0, 7, 0, 4, 0, 0, 2},
                       {0, 0, 7, 0, 9, 14, 0, 0, 0},
                       {0, 0, 0, 9, 0, 10, 0, 0, 0},
                       {0, 0, 4, 14, 10, 0, 2, 0, 0},
                       {0, 0, 0, 0, 0, 2, 0, 1, 6},
                       {8, 11, 0, 0, 0, 0, 1, 0, 7},
                       {0, 0, 2, 0, 0, 0, 6, 7, 0}};

    dijkstra(graph, 0);

    return 0;
}

以上示例演示了如何使用迪杰斯特拉算法找到带权有向图中从源顶点到其他顶点的最短路径。在上述示例中，我们使用了一个9个顶点的图，并使用邻接矩阵来表示图的连接关系。你可以根据自己的需求调整图的大小和边的权重。运行程序后，将输出每个顶点到源顶点的最短距离。