字符串类型C语言迪杰斯特拉算法输出最短路径

一般来说，Dijkstra 算法是用于求解带权图的最短路径问题，其中的边权通常是数字类型的。不过，如果我们将字符串类型的边权先转换成数字类型，再应用 Dijkstra 算法，同样可以求解最短路径问题。下面是一个示例代码：

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

#define V 5 // 图的顶点数
#define INF INT_MAX // 表示无穷大

// 函数：将字符串转换成数字
int str2num(char* str)
{
    int num = 0;
    for (int i = 0; i < strlen(str); i++) {
        num = num * 10 + (str[i] - '0');
    }
    return num;
}

// 函数：迪杰斯特拉算法求解最短路径
void dijkstra(int graph[V][V], int src)
{
    int dist[V]; // 存储源点到每个顶点的最短距离
    int visited[V] = {0}; // 标记每个顶点是否已被访问

    // 初始化
    for (int i = 0; i < V; i++) {
        dist[i] = INF;
    }
    dist[src] = 0;

    // 按照最短距离依次访问每个顶点
    for (int count = 0; count < V - 1; count++) {
        // 找到当前未访问过的距离源点最近的顶点
        int minDist = INF;
        int minIndex = -1;
        for (int i = 0; i < V; i++) {
            if (!visited[i] && dist[i] < minDist) {
                minDist = dist[i];
                minIndex = i;
            }
        }

        // 标记该顶点已被访问
        visited[minIndex] = 1;

        // 更新与该顶点相邻的顶点的最短距离
        for (int i = 0; i < V; i++) {
            if (!visited[i] && graph[minIndex][i] != 0 && dist[minIndex] != INF
                    && dist[minIndex] + graph[minIndex][i] < dist[i]) {
                dist[i] = dist[minIndex] + graph[minIndex][i];
            }
        }
    }

    // 输出结果
    printf("最短距离：\n");
    for (int i = 0; i < V; i++) {
        if (dist[i] == INF) {
            printf("%d 到 %d 不存在路径\n", src, i);
        } else {
            printf("%d 到 %d 的最短距离为 %d\n", src, i, dist[i]);
        }
    }
}

// 主函数
int main()
{
    // 用邻接矩阵表示图
    int graph[V][V] = {
        {0, str2num("25"), 0, str2num("12"), str2num("34")},
        {str2num("25"), 0, str2num("11"), 0, 0},
        {0, str2num("11"), 0, 0, str2num("22")},
        {str2num("12"), 0, 0, 0, str2num("17")},
        {str2num("34"), 0, str2num("22"), str2num("17"), 0}
    };

    dijkstra(graph, 0); // 从顶点0开始求解最短路径

    return 0;
}

需要注意的是，这里我们假设字符串只包含数字字符，如果包含其他字符，需要对输入字符串进行验证和转换处理。