Dijkstra算法和Floyd算法求最短路径

1.Dijkstra算法
Dijkstra算法用于从一个起始节点到图中所有其他节点的最短路径。它使用贪心策略逐步扩展路径，并选择当前路径中最短的节点作为下一个节点。Dijkstra算法来计算起始节点到各个节点的最短距离。Dijkstra算法适用于有向图或无向图，但是对于权重为负的边，Dijkstra算法不适用。
求解步骤:①初始化距离数组和访问数组，将起始节点的距离值设置为0，其他节点的距离值设置为无穷大，访问数组初始化为false。②从起始节点开始，选择当前距离值最小的节点，将其标记为已访问。③遍历该节点的邻居节点，如果通过当前节点到达邻居节点的路径比之前的路径更短，则更新邻居节点的距离值。④重复上述步骤，选择下一个距离值最小的未访问节点，直到所有节点都被标记为已访问，或者找到了目标节点。输出最短路径结果，即起始节点到其他节点的最短距离。
代码示例：

#include 
#include 
#define INF 9999
#define V 6

void dijkstra(int graph[V][V], int start) {
    int dist[V]; // 存储起始节点到各个节点的最短距离
    bool visited[V]; // 记录节点是否已访问
    int i, j, min, u;
    
    // 初始化距离数组和访问数组
    for (i = 0; i < V; i++) {
        dist[i] = INF;
        visited[i] = false;
    }
    
    // 设置起始节点距离为0
    dist[start] = 0;
    
    // 寻找最短路径
    for (i = 0; i < V - 1; i++) {
        min = INF;
        for (j = 0; j < V; j++) {
            if (!visited[j] && dist[j] < min) {
                min = dist[j];
                u = j;
            }
        }
        
        visited[u] = true;
        
        for (j = 0; j < V; j++) {
            if (!visited[j] && graph[u][j] != INF && dist[u] + graph[u][j] < dist[j]) {
                dist[j] = dist[u] + graph[u][j];
            }
        }
    }
    
    // 打印最短路径结果
    printf("节点  最短距离\n");
    for (i = 0; i < V; i++) {
        printf("%d %d\n", i, dist[i]);
    }
}

int main() {
    int graph[V][V] = {
        {0, 1, 4, INF, INF, INF},
        {1, 0, 2, 7, 5, INF},
        {4, 2, 0, INF, 1, INF},
        {INF, 7, INF, 0, 3, 2},
        {INF, 5, 1, 3, 0, 6},
        {INF, INF, INF, 2, 6, 0}
    };
    
    int start = 0; // 起始节点
    dijkstra(graph, start);
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

2.Floyd算法：
Floyd算法用于计算图中任意两个节点之间的最短路径。它采用动态规划的思想，通过中间节点的遍历来更新最短路径。适用于有向图或无向图，并且可以处理权重为负的边，但是对于包含负权重环的图，Floyd算法不适用。
求解步骤：①初始化距离矩阵，其中的元素表示两个节点之间的直接距离。如果两个节点之间没有直接连接，则距离为无穷大。②使用动态规划的思想，通过中间节点的遍历来更新节点之间的最短路径。③对于每一对节点，通过考虑是否经过一个中间节点，更新它们之间的距离。如果通过中间节点得到的路径比之前的路径更短，则更新距离矩阵中的值。④重复上述步骤，遍历所有的节点作为中间节点。
输出最短路径结果，即任意两个节点之间的最短距离。
代码示例:

#include 
#define INF 9999
#define V 4

void floyd(int graph[V][V]) {
    int dist[V][V]; // 存储最短路径距离
    int i, j, k;

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

    // 寻找最短路径
    for (k = 0; k < V; k++) {
        for (i = 0; i < V; i++) {
            for (j = 0; j < V; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // 打印最短路径结果
    printf("节点对 最短距离\n");
    for (i = 0; i < V; i++) {
        for (j = 0; j < V; j++) {
            if (dist[i][j] == INF) {
                printf("%d 到 %d INF\n", i, j);
            } else {
                printf("%d 到 %d %d\n", i, j, dist[i][j]);
            }
        }
    }
}

int main() {
    int graph[V][V] = {
        {0, 3, INF, 7},
        {8, 0, 2, INF},
        {5, INF, 0, 1},
        {2, INF, INF, 0}
    };

    floyd(graph);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51