C语言实现Dijkstra算法经过指定点

下面是 C 语言实现 Dijkstra 算法经过指定点的代码：

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

#define V 6 // 图中顶点的数量

int minDistance(int dist[], bool sptSet[])
{
    int min = INT_MAX, min_index;

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

    return min_index;
}

void printSolution(int dist[])
{
    printf("Vertex \t Distance from Source\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 dest)
{
    int dist[V];
    bool sptSet[V];

    for (int i = 0; i < V; i++)
    {
        dist[i] = INT_MAX;
        sptSet[i] = false;
    }

    dist[src] = 0;

    for (int count = 0; count < V - 1; count++)
    {
        int u = minDistance(dist, sptSet);

        sptSet[u] = true;

        for (int v = 0; v < V; v++)
        {
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])
            {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    // 如果指定点不是终点，那么需要重新计算最短路径
    if (dest != INT_MAX && dist[dest] != INT_MAX)
    {
        int dist_dest = dist[dest];

        for (int i = 0; i < V; i++)
        {
            dist[i] = INT_MAX;
            sptSet[i] = false;
        }

        dist[dest] = 0;

        for (int count = 0; count < V - 1; count++)
        {
            int u = minDistance(dist, sptSet);

            sptSet[u] = true;

            for (int v = 0; v < V; v++)
            {
                if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])
                {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }

        // 将最短路径和指定点到终点的距离相加
        for (int i = 0; i < V; i++)
        {
            if (i != dest && graph[dest][i] != 0 && dist[i] != INT_MAX)
            {
                dist[i] += graph[dest][i];
            }
        }

        dist[dest] = dist_dest;
    }

    printSolution(dist);
}

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

    dijkstra(graph, 0, 4);

    return 0;
}

注：在本例中，指定点为 4。如果指定点不是终点，则需要重新计算最短路径，将最短路径和指定点到终点的距离相加。