Dijkstra算法解题方法与C语言编程

Dijkstra算法的的简介就不再写了，已经有很多比较好的资源讲述了Dijkstra算法的原理与步骤。

本博客直接讲述解题方式和代码编程。

一、Dijkstra解题

ps：忽略丑字，写这两个把我折磨惨了~

二、C语言编程

针对上面的问题来进行C语言编程，直接上代码

1、dijkstra.c：

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

#define NUMS 8   
#define INF 65535

typedef struct  
{   
    	char vertex[NUMS];  
	char fVertex[NUMS];
	int distance[NUMS]; 
    	int edges[NUMS][NUMS];   
    	int n,e;   
}Graph;   

void Ppath(Graph G);

void ReadGraph(Graph *G)   
{   
	int i,j;
	FILE * fp = fopen("dij.txt","r");
	G->n = NUMS;
	G->e = NUMS * NUMS; 
	for(i=0; i<NUMS; i++)
	{
		for(j=0; j<NUMS; j++)
		{
			fscanf(fp,"%d",&(G->edges[i][j]));		
		}
	}
}   

void Djikstra(Graph G)
{
	int i,j,k,tmp;

	for(i=0; i<NUMS; i++)
	{
		G.distance[i] = INF;
		G.vertex[i] = 0;
		G.fVertex[i] = 0;
	}

	G.distance[0] = 0;
	
	for(i=0; i<NUMS; i++)
	{
		tmp = INF;

		for(j=0; j<NUMS; j++)
		{
			if(G.vertex[j] == 0 && G.distance[j] < tmp)
			{

				tmp = G.distance[j];
				k = j;
			}
		}

		G.vertex[k] = 1; 
		
		for(j=0; j<NUMS; j++)
		{
			if(G.edges[k][j]!=0 && G.vertex[j]==0 && G.distance[j] > G.distance[k]+G.edges[k][j])
			{
				G.distance[j] = G.distance[k] + G.edges[k][j];
				G.fVertex[j] = k;
			}
		}
	}
	
	Ppath(G);
	
}

void Ppath(Graph G)
{
	int i;
	printf("顶点1与各点之间的最短距离分别分:\n");
	for(i=0; i<NUMS; i++)
	{
		printf("%d  ",G.distance[i]);
	}
	printf("\n");

	printf("顶点1与各点之间的最短路径分别为:\n");
	for(i=1; i<NUMS; i++)
	{
		printf("%d <- ",i+1);
		int tmp = G.fVertex[i];
		while(tmp != 0)
		{
			printf("%d <- ",tmp+1);
			tmp = G.fVertex[tmp];
		}
		printf("1\n");
	}
	printf("\n");	
}

int main()
{
	Graph G;
	ReadGraph(&G);
	Djikstra(G);
	return 0;
}

2、dij.txt：

0	2	65535	3	65535	65535	65535	65535
2	0	1	65535	4	65535	65535	65535
65535	1	0	5	65535	1	65535	65535
3	65535	5	0	65535	65535	3	65535
65535	4	65535	65535	0	3	65535	2
65535	65535	1	65535	3	0	2	1
65535	65535	65535	3	65535	2	0	3
65535	65535	65535	65535	2	1	3	0

3、运行结果：

三、总结

可以看到手动计算结果与编程完成的结果一致，直接替换掉dij.txt，更改代码中的NUMS便可实现自己的计算~

再贴几个讲解Dijkstra算法原理的博客吧：

1、其实百度百科挺详细

https://baike.baidu.com/item/迪杰斯特拉算法/4049057?fr=aladdin

2、简单易懂——Dijkstra算法讲解

https://blog.csdn.net/qq_39521554/article/details/79333690