一个六阶完全图的汉密尔顿路及最短路径C语言

以下是一个六阶完全图的汉密尔顿路及最短路径的C语言实现示例：

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

// 定义图中最大顶点数
#define MAX_VERTICES 6

// 定义无穷大值
#define INFINITY INT_MAX

// 定义图的邻接矩阵
int graph[MAX_VERTICES][MAX_VERTICES] = {
    {0, 1, 1, 1, 1, 1},
    {1, 0, 1, 1, 1, 1},
    {1, 1, 0, 1, 1, 1},
    {1, 1, 1, 0, 1, 1},
    {1, 1, 1, 1, 0, 1},
    {1, 1, 1, 1, 1, 0}
};

// 定义顶点数和边数
int num_vertices = MAX_VERTICES, num_edges = MAX_VERTICES * (MAX_VERTICES - 1) / 2;

// 记录访问过的顶点
int visited[MAX_VERTICES];

// 查找最短路径
void dijkstra(int start, int end) {
    int distance[MAX_VERTICES], i, j, min_distance, next_vertex;

    // 初始化距离数组和访问数组
    for(i = 0; i < num_vertices; i++) {
        distance[i] = INFINITY;
        visited[i] = 0;
    }

    // 设置起点距离为0
    distance[start] = 0;

    // 查找最短路径
    for(i = 0; i < num_vertices - 1; i++) {
        min_distance = INFINITY;

        for(j = 0; j < num_vertices; j++) {
            if(!visited[j] && distance[j] < min_distance) {
                min_distance = distance[j];
                next_vertex = j;
            }
        }

        visited[next_vertex] = 1;

        for(j = 0; j < num_vertices; j++) {
            if(!visited[j] && graph[next_vertex][j] != INFINITY && distance[next_vertex] + graph[next_vertex][j] < distance[j]) {
                distance[j] = distance[next_vertex] + graph[next_vertex][j];
            }
        }
    }

    // 输出结果
    printf("最短路径长度为：%d\n", distance[end]);
}

// 判断是否存在汉密尔顿路
int isHamiltonian(int path[], int pos) {
    int i, j;

    // 判断是否经过了所有顶点
    if(pos == num_vertices) {
        // 判断起点和终点是否相同
        if(path[0] == path[num_vertices - 1]) {
            return 1;
        }
        else {
            return 0;
        }
    }

    for(i = 0; i < num_vertices; i++) {
        // 判断顶点是否可达且未被访问过
        if(graph[path[pos - 1]][i] != INFINITY && !visited[i]) {
            visited[i] = 1;
            path[pos] = i;

            // 递归查找
            if(isHamiltonian(path, pos + 1)) {
                return 1;
            }

            // 回溯
            visited[i] = 0;
        }
    }

    return 0;
}

// 查找汉密尔顿路
void hamiltonian() {
    int path[MAX_VERTICES], i;

    // 初始化访问数组
    for(i = 0; i < num_vertices; i++) {
        visited[i] = 0;
    }

    // 设置起点
    path[0] = 0;
    visited[0] = 1;

    // 查找汉密尔顿路
    if(isHamiltonian(path, 1)) {
        printf("存在汉密尔顿路：");
        for(i = 0; i < num_vertices; i++) {
            printf("%d ", path[i]);
        }
        printf("\n");
    }
    else {
        printf("不存在汉密尔顿路\n");
    }
}

// 主函数
int main() {
    int start, end;

    // 查找最短路径
    printf("请输入起点和终点：");
    scanf("%d %d", &start, &end);
    dijkstra(start, end);

    // 查找汉密尔顿路
    hamiltonian();

    return 0;
}

这个示例中，我们直接使用了完全图的邻接矩阵表示。在实际应用中，我们需要先创建图，再进行汉密尔顿路和最短路径的查找。