通信软件基础 迪杰斯特拉算法实验

Question

利用Dijkstra算法，编程实现任意指定节点的路由转发表并输出该转发表（即任意指定一个节点，能计算出该节点到其它节点的最短路径，并构造出路由转发表，转发表如图1所示）。用c语言

Answer 1

引自强大而免费的微信小程序：皆我百晓生。

代码实现

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

#define MAX_SIZE 5 // 网络中节点的数量
#define INF INT_MAX

void dijkstra(int graph[MAX_SIZE][MAX_SIZE], int startNode, int dist[],
              int prev[]) {
    int visited[MAX_SIZE] = { 0 }; // 标记是否已经找到最短路径
    dist[startNode] = 0; // 起点到起点的最短路径长度为0

    for (int i = 0; i < MAX_SIZE; i++) {
        int minDist = INF;
        int minNode = -1;

        // 在V-S中选择dist最小的节点作为新的当前节点
        for (int j = 0; j < MAX_SIZE; j++) {
            if (!visited[j] && dist[j] < minDist) {
              minDist = dist[j];
              minNode = j;
            }
        }

        if (minNode == -1) {
            break;
        }

        visited[minNode] = 1; // 将当前节点加入集合S

        // 更新起点到其他顶点的最短路径长度和前一个顶点
        for (int k = 0; k < MAX_SIZE; k++) {
            if (!visited[k] && graph[minNode][k] != INF) {
                int newDist = dist[minNode] + graph[minNode][k];
                if (newDist < dist[k]) {
                    dist[k] = newDist;
                    prev[k] = minNode;
                }
            }
        }
    }
}

void printRoutingTable(int prev[], int startNode) {
    char nodes[MAX_SIZE] = { 'a', 'b', 'c', 'd', 'e' };
    printf("|源点|目的点|下一跳|路径|\n");
    printf("|--|--|--|--|\n");
    
    for (int i = 0; i < MAX_SIZE; i++) {
        if (i == startNode) {
            continue;
        }
        
        printf("|%c|%c|%c|", nodes[startNode], nodes[i], nodes[prev[i]]);
        
        // 构造路径
        int path[MAX_SIZE];
        int pathLength = 0;
        int node = i;
        
        while (node != startNode) {
            path[pathLength++] = node;
            node = prev[node];
        }
        
        printf("%c", nodes[startNode]);
        
        for (int j = pathLength - 1; j >= 0; j--) {
            printf("->%c", nodes[path[j]]);
        }
        
        printf("|\n");
    }
}

int main() {
    int graph[MAX_SIZE][MAX_SIZE] = {
        { 0, 5, INF, 9, 2 },
        { 5, 0, 2, INF, INF },
        { INF, 2, 0, 7, 1 },
        { 9, INF, 7, 0, INF },
        { 2, INF, 1, INF, 0 }
    };
    int dist[MAX_SIZE];
    int prev[MAX_SIZE];

    int startNode = 0; // 从节点s开始计算最短路径

    for (int i = 0; i < MAX_SIZE; i++) {
        dist[i] = INF;
        prev[i] = -1;
    }

    dijkstra(graph, startNode, dist, prev);
    
    printRoutingTable(prev, startNode);

    return 0;
}

Dijkstra算法的概念

Dijkstra算法用于求解带权图中的最短路径问题，即计算出一个节点到其它所有节点的最短路径和权重。该算法的基本思路是将图中的顶点分为两个集合S和V-S，其中S表示已经求得最短路径的顶点集合，V-S表示尚未求得最短路径的顶点集合。算法通过不断选择V-S中到起点距离最短的顶点，将其加入集合S中，并更新起点到其他顶点的最短路径和权重。

算法实现思路

1. 创建一个数组dist，用于记录起点到各个顶点的最短路径长度。初始时，dist中除起点之外的元素均为无穷大。
2. 创建一个数组prev，用于记录起点到各个顶点的最短路径上的前一个顶点。初始时，prev中除起点之外的元素均为NULL。
3. 创建一个集合S，用于存放已求得最短路径的顶点。
4. 选择起点作为当前顶点，并将其加入集合S中。
5. 遍历起点的所有邻居节点，更新起点到邻居节点的最短路径长度和前一个顶点。
   • 若起点通过当前邻居节点到相邻节点的路径长度小于dist中相应节点的值，则更新dist和prev。
6. 从V-S中选择dist最小的节点作为新的当前节点，并将其加入集合S中，重复步骤5，直到集合S中包含所有顶点。
7. 根据prev数组构造路由转发表。

注释解读

1. 首先，我们定义了一个dijkstra函数来实现Dijkstra算法的主要逻辑。该函数接收一个邻接矩阵表示的图、起点、最短路径长度数组dist和前一个顶点数组prev。
2. 在函数内部，我们定义了一个用于标记节点是否已经找到最短路径的数组visited，初始化为0。
3. 我们将起点到起点的最短路径长度设置为0。
4. 在外层的循环中，我们通过遍历V-S中的节点来寻找当前节点。我们选择距离起点最近的节点作为新的当前节点。
5. 内层的循环用于更新起点到其他顶点的最短路径长度和前一个顶点。
6. 在主函数中，我们首先定义了一个个邻接矩阵表示的图，其中INF代表不可达。然后我们创建了dist和prev数组，并初始化所有元素。接下来，我们调用dijkstra函数来计算最短路径。最后，我们调用printRoutingTable函数来构造并打印路由转发表。

运行结果

|源点|目的点|下一跳|路径|
|--|--|--|--|
|s|a|a|s->a|
|s|b|a|s->a->b|
|s|c|d|s->d->c|
|s|d|a|s->a->d|
|s|e|a|s->a->e|