c语言输入：多段图的代价矩阵；输出：最短长度及路径各个节点。给出源代码，算法设计思路，总结

算法设计思路：

本题使用Dijkstra算法求解最短路径。Dijkstra算法的基本思想是：对于图中任意两个顶点，初始时设置一个起点，将其到各个顶点的距离赋初值（如果有边相连，则赋上边的长度，否则为无限大）。然后标记起点为已经处理过的点，找到离起点最近的未处理过的点，将该点标记为已经处理过，并更新与该点相邻的点的距离（如果更优则更新）。重复上述操作，直到所有顶点都被标记为已经处理过，或者剩余的点到起点的距离是无穷大。

源代码如下：

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

#define MAX_VERTICES 1000

int graph[MAX_VERTICES][MAX_VERTICES]; // 多段图的代价矩阵
int dist[MAX_VERTICES]; // 起点到各个节点的距离
int prev[MAX_VERTICES]; // 记录最短路径

void dijkstra(int start, int end, int n) {
    int visited[MAX_VERTICES] = {0}; // 记录节点是否被访问过
    int i, j, k;
    int min_dist, min_index;

    for (i = 0; i < n; i++) {
        dist[i] = INT_MAX; // 初始化距离为无穷大
        prev[i] = -1; // 初始化前驱节点为-1
    }

    dist[start] = 0; // 起点到自己的距离为0

    for (i = 0; i < n; i++) {
        min_dist = INT_MAX;
        min_index = -1;

        // 找到未访问过的距离最小的节点
        for (j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                min_index = j;
            }
        }

        if (min_index == -1) {
            break; // 所有节点都被访问过了
        }

        visited[min_index] = 1; // 标记节点为已访问

        // 更新与该节点相邻的节点的距离
        for (k = 0; k < n; k++) {
            if (graph[min_index][k] > 0 && !visited[k] && dist[min_index] + graph[min_index][k] < dist[k]) {
                dist[k] = dist[min_index] + graph[min_index][k];
                prev[k] = min_index;
            }
        }
    }

    printf("最短长度：%d\n", dist[end]);

    // 输出路径上的节点
    printf("路径节点：");
    int path[MAX_VERTICES];
    int path_index = 0;
    int node = end;
    while (node != start) {
        path[path_index++] = node;
        node = prev[node];
    }
    path[path_index] = start;
    for (i = path_index; i >= 0; i--) {
        printf("%d ", path[i]);
    }
    printf("\n");
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    int i, j;
    int u, v, w;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            graph[i][j] = 0; // 初始化为0
        }
    }

    for (i = 0; i < m; i++) {
        scanf("%d %d %d", &u, &v, &w);
        graph[u][v] = w;
    }

    int start, end;
    scanf("%d %d", &start, &end);

    dijkstra(start, end, n);

    return 0;
}

总结：

本题使用Dijkstra算法求解最短路径，时间复杂度为O(n^2)，空间复杂度为O(n^2)。算法的基本思想是：对于图中任意两个顶点，初始时设置一个起点，将其到各个顶点的距离赋初值（如果有边相连，则赋上边的长度，否则为无限大）。然后标记起点为已经处理过的点，找到离起点最近的未处理过的点，将该点标记为已经处理过，并更新与该点相邻的点的距离（如果更优则更新）。重复上述操作，直到所有顶点都被标记为已经处理过，或者剩余的点到起点的距离是无穷大。