汉密尔顿路及最短路径C语言

汉密尔顿路可以理解为一条经过图中所有顶点恰好一次的路径，而最短路径可以理解为两个顶点之间的路径长度最短。下面是一份使用C语言实现的汉密尔顿路及最短路径的代码示例：

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

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

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

// 定义图的邻接矩阵
int graph[MAX_VERTICES][MAX_VERTICES];

// 定义顶点数和边数
int num_vertices, num_edges;

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

// 初始化图的邻接矩阵
void initGraph() {
    int i, j;
    for(i = 0; i < num_vertices; i++) {
        for(j = 0; j < num_vertices; j++) {
            graph[i][j] = INFINITY;
        }
    }
}

// 添加边
void addEdge(int start, int end, int weight) {
    graph[start][end] = weight;
    graph[end][start] = weight;
}

// 查找最短路径
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("存在汉密尔顿路\n");
    }
    else {
        printf("不存在汉密尔顿路\n");
    }
}

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

    // 输入顶点数和边数
    printf("请输入顶点数和边数：");
    scanf("%d %d", &num_vertices, &num_edges);

    // 初始化图的邻接矩阵
    initGraph();

    // 输入边的信息
    printf("请输入边的信息：\n");
    for(i = 0; i < num_edges; i++) {
        printf("边%d：", i + 1);
        scanf("%d %d %d", &start, &end, &weight);
        addEdge(start, end, weight);
    }

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

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

    return 0;
}