C语言求不带权无向连通图从顶点1-4的一条最短路径

可以使用Dijkstra算法来求解不带权无向连通图中从顶点1到顶点4的一条最短路径。具体步骤如下：

1. 初始化距离数组dist，将所有顶点的距离初始化为无穷大，将起点1的距离设为0。

2. 创建一个空堆heap，将起点1加入堆中。

3. 当堆不为空时，取出堆顶元素u，遍历u的所有邻居v，如果从起点1到v的距离比dist[v]更短，则更新dist[v]的值，并将v加入堆中。

4. 重复步骤3直到堆为空或者堆顶元素是终点4。

5. 如果dist[4]的值为无穷大，则表示从起点1无法到达终点4。否则，可以通过反向遍历记录路径，从终点4一直走到起点1，即可得到一条从1到4的最短路径。

以下是C语言实现示例代码：

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

#define N 5

int graph[N][N] = {
    {0, 1, 1, 0, 0},
    {1, 0, 1, 1, 0},
    {1, 1, 0, 1, 0},
    {0, 1, 1, 0, 1},
    {0, 0, 0, 1, 0}
};

int dist[N];
int visited[N];

typedef struct {
    int vertex;
    int distance;
} Node;

Node heap[N];
int heap_size = 0;

void swap(Node *a, Node *b) {
    Node temp = *a;
    *a = *b;
    *b = temp;
}

void push(Node node) {
    heap[heap_size++] = node;
    int i = heap_size - 1;
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (heap[parent].distance > heap[i].distance) {
            swap(&heap[parent], &heap[i]);
            i = parent;
        } else {
            break;
        }
    }
}

Node pop() {
    Node result = heap[0];
    heap[0] = heap[--heap_size];
    int i = 0;
    while (i * 2 + 1 < heap_size) {
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        int child = left;
        if (right < heap_size && heap[right].distance < heap[left].distance) {
            child = right;
        }
        if (heap[child].distance < heap[i].distance) {
            swap(&heap[child], &heap[i]);
            i = child;
        } else {
            break;
        }
    }
    return result;
}

void dijkstra(int start, int end) {
    for (int i = 0; i < N; i++) {
        dist[i] = INT_MAX;
    }
    dist[start] = 0;
    push((Node){start, 0});
    while (heap_size > 0) {
        Node node = pop();
        if (visited[node.vertex]) {
            continue;
        }
        visited[node.vertex] = 1;
        if (node.vertex == end) {
            return;
        }
        for (int i = 0; i < N; i++) {
            if (graph[node.vertex][i]) {
                int alt = dist[node.vertex] + 1;
                if (alt < dist[i]) {
                    dist[i] = alt;
                    push((Node){i, alt});
                }
            }
        }
    }
}

int main() {
    dijkstra(0, 3);
    if (dist[3] == INT_MAX) {
        printf("No path from 1 to 4\n");
    } else {
        printf("Shortest path from 1 to 4 is %d\n", dist[3]);
    }
    return 0;
}

这段代码会输出从顶点1到顶点4的最短路径长度。如果路径不存在，则会输出"No path from 1 to 4"。