NOJ数据结构022——Dijkstra算法

短命女 2022-10-15 04:46 159阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][202105231545352.png]  
本题要求使用dijkstra（迪杰斯特拉）算法，这是基于广度优先搜索的贪心算法，可以用于求取源点到各点的最小路径（权重皆正的情况下），若有权重为负，则使用弗洛伊德算法。

最后还要进行按路径从小到大的顺序输出。

代码：

#include <stdio.h>
    #include <stdlib.h>
    
    #define MAX_VER_NUM 2000
    
    typedef enum {
         DG, UDG, DN, UDN }GraphKind;
    
    typedef struct ArcNode{
        
    	int adjvex;
    	struct ArcNode* nextarc;
    	int weight;
    }ArcNode;
    
    typedef struct {
        
    	int data;
    	ArcNode* firstarc;
    }VexNode;
    
    typedef struct {
        
    	VexNode vertex[MAX_VER_NUM];
    	int num_arc, num_vex;
    	GraphKind kind;
    }AdjList;
    
    typedef struct {
        
    	int visited[MAX_VER_NUM];
    	int length[MAX_VER_NUM];
    }Path;
    
    AdjList* CreateGraph(int n, int m);     //创建有向网
    void InitPath(AdjList A, Path* dist);   //初始化dist数组
    int JudgePath(AdjList A, Path* dist);   //判断是否遍历过
    int FindMinPath(AdjList A, Path* dist); //寻找最短路径的位置
    void UpdatePath(AdjList A, Path* dist, int num_minpath);//更新路径
    void dijkstra(AdjList A, Path* dist);   //dijkstra算法
    void PrintDist(AdjList A, Path dist);   //打印最短路径
    
    int main()
    {
        
    	int n, m;
    	scanf("%d%d", &n, &m);
    	AdjList* A;
    	A = CreateGraph(n, m);
    	Path dist;
    	dijkstra(*A, &dist);
    	PrintDist(*A, dist);
    	return 0;
    }
    
    AdjList* CreateGraph(int n, int m)
    {
           //创建有向网
    	AdjList* A;
    	A = (AdjList*)malloc(sizeof(AdjList));
    	if (A == NULL) {
        
    		return NULL;
    	}
    	A->kind = DN;
    	A->num_vex = n;
    	A->num_arc = m;
    	for (int i = 0; i < A->num_vex; i++) {
        
    		A->vertex[i].data = i + 1;
    		A->vertex[i].firstarc = NULL;
    	}
    	int v1, v2, w;
    	for (int i = 0; i < A->num_arc; i++) {
        
    		scanf("%d%d%d", &v1, &v2, &w);
    		ArcNode* tmp;
    		tmp = (ArcNode*)malloc(sizeof(ArcNode));
    		if (tmp == NULL) {
        
    			return NULL;
    		}
    		tmp->adjvex = v2;
    		tmp->weight = w;
    		tmp->nextarc = A->vertex[v1 - 1].firstarc;
    		A->vertex[v1 - 1].firstarc = tmp;
    	}
    	return A;
    }
    
    void InitPath(AdjList A, Path *dist)
    {
           //初始化dist数组
    	dist->visited[0] = 0;
    	dist->length[0] = 0;
    	for (int i = 1; i < A.num_vex; i++) {
        
    		dist->visited[i] = -1;
    		dist->length[i] = -1;
    	}
    	ArcNode* tmp;
    	tmp = A.vertex[0].firstarc;
    	while (tmp) {
        
    		dist->visited[tmp->adjvex - 1] = 1;
    		dist->length[tmp->adjvex - 1] = tmp->weight;
    		tmp = tmp->nextarc;
    	}
    }
    
    int JudgePath(AdjList A, Path* dist)
    {
           //判断是否遍历过
    	for (int i = 0; i < A.num_vex; i++) {
        
    		if (dist->visited[i] == 1) {
        
    			return 1;
    		}
    	}
    	return 0;
    }
    
    int FindMinPath(AdjList A, Path* dist)
    {
           //寻找最短路径的位置
    	int min = MAX_VER_NUM, num_minpath;
    	for (int i = 0; i < A.num_vex; i++) {
        
    		if (dist->visited[i] == 1) {
        
    			if (dist->length[i] < min) {
        
    				min = dist->length[i];
    				num_minpath = i;
    			}
    		}
    	}
    	return num_minpath;
    }
    
    void UpdatePath(AdjList A, Path* dist, int num_minpath)
    {
           //更新路径
    	ArcNode* tmp;
    	int minpath = dist->length[num_minpath];
    	tmp = A.vertex[num_minpath].firstarc;
    	dist->visited[num_minpath] = 0;
    	while (tmp) {
        
    		if (dist->visited[tmp->adjvex - 1] == 1) {
        
    			if (minpath + tmp->weight < dist->length[tmp->adjvex - 1]) {
        
    				dist->length[tmp->adjvex - 1] = minpath + tmp->weight;
    			}
    		}
    		else if (dist->visited[tmp->adjvex - 1] == -1) {
        
    			dist->visited[tmp->adjvex - 1] = 1;
    			dist->length[tmp->adjvex - 1] = tmp->weight + minpath;
    		}
    		tmp = tmp->nextarc;
    	}
    }
    
    void dijkstra(AdjList A, Path *dist)
    {
           //dijkstra算法
    	InitPath(A, dist);
    	while (JudgePath(A, dist)) {
        
    		int min = FindMinPath(A, dist);
    		UpdatePath(A, dist, min);
    	}
    }
    
    void PrintDist(AdjList A, Path dist)
    {
           //打印最短路径
    	int tmp = 0, min = 0;
    	int count = 0;
    	for (int i = 0; i < A.num_vex; i++) {
        
    		if (dist.visited[i] == -1) {
        
    			count++;
    		}
    	}
    	for (int i = 1; i < A.num_vex - count; i++) {
        
    		for (int j = 1; j < A.num_vex; j++) {
        
    			if (dist.visited[j] == 0) {
        
    				min = dist.length[j];
    				tmp = j;
    				break;
    			}
    		}
    		for (int j = 1; j < A.num_vex; j++) {
        
    			if (dist.visited[j] == 0 && min > dist.length[j]) {
        
    				min = dist.length[j];
    				tmp = j;
    			}
    		}
    		dist.visited[tmp] = -2;
    		printf("1 %d %d\n", tmp + 1, dist.length[tmp]);
    	}
    	for (int i = 0; i < A.num_vex; i++) {
        
    		if (dist.visited[i] == -1) {
        
    			printf("1 %d -1", i + 1);
    		}
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]: /images/20221014/8c269e94755d46d7929c40e6d28a7075.png
[202105231545352.png]: /images/20221014/d518d723164449feb0f80b28b790aa17.png