Dijkstra最短路径算法C语言实现

输入各结点构成的邻接矩阵及开始结点，计算出该节点到其他各节点之间的最短距离。也可计算某一开始结点到指定结点的最短距离。

#include 

#define SIZE 110   //定义最大结点数 
#define INF  1000000;  //定义最大路径长度 
 
int nm;     //定义结点数和路径数 

void dijkstra（int g[SIZE][SIZE]int nint from）;  //输出开始结点到其他个点的路径及路径长度（字符） 
//int search（int map[SIZE][SIZE]int fromint to）;  //输出指定两结点（源点到终点）的路径长度 


int main（）{       //主函数部分 
	int ij;
	//调用dijkstra函数的主函数部分 
	int g[SIZE][SIZE];
	char startnode;  //定义字符型开始结点，以便将整型数字转换成字符型输出 
	printf（“  输入结点数n和路径数m:“）; 
	scanf（“%d%d“&n&m）;
	printf（“\n  输入图的邻接矩阵:\n“）;
	for（i = 1;i <= n;i ++）{
		for（j =1;j <= n;j ++）
		  scanf（“ %d“&g[i][j]）;  //若两节点间没有直接路径，则输入数字0；反之则输入路径长度； 
	}
	printf（“\n  输入开始结点:“）;
	fflush（stdin）;    //每次输入后缓冲区会遗留回车符‘\n‘，执行getchar前先清空缓冲区
	startnode = getchar（）;    //单个字符输入 
	startnode = startnode - ‘@‘; //将字符ABCD等用1234等代替输入 。@的ASCII码为64 
	dijkstra（gnstartnode）;   //调用函数输出开始结点到各结点的路径及路径长度
	
	
	 
	/*//调用search函数的主函数部分 
	int map[SIZE][SIZE];
	for（i = 1;i <= n;++ i）{
		for（j = 1;j <= n;++ j）
		 map[i][j] = INF;  //初始化两结点间的路径长度均为无穷大 
	}
	
	int abc;

	for（i = 1;i <= m;++ i）{
		printf（“\n  输入两个结点ab及其路径长度c:“）;
		scanf（“%d%d%d“&a&b&c）;
		map[a][b] = map[b][a] = c;   //改变有直接路径的两结点间的路径长度 
	}
	printf（“\n输出图的邻接矩阵:“）;
	for（i = 1;i <= n;i ++）{
	  for（j =1;j <= n;j ++）
	    printf（“ %d “g[i][j]）;
	    printf（“\n“）;
    }
	int fromto;
	printf（“  输入源点from和终点to:“）;
	scanf（“%d%d“&from&to）;
	int an = search（mapfromto）;  //调用函数获取最短路径 
	printf（“  从源点到终点的最短路径长度an为:“）;
	printf（“%d“an）;*/
	
	return 0;
}


void dijkstra（int g[SIZE][SIZE]int nint from）{  //输出开始结点到其他个点的路径及路径长度 

	int line[SIZE][SIZE]distance[SIZE]pred[SIZE]; 
	int visited[SIZE]countminnextnodeij;
		
	for（i = 1;i <= n;i ++）{
		for（j = 1;j <= n;j ++）{
			if（g[i][j] == 0）{ //若输入的路径长度为0，则将其更新为无穷大；反之则依旧为路径长度 
				line[i][j] = INF;
			}
			else{
				line[i][j] = g[i][j];
			}
		}
	}
	
	for（i = 1;i <= n;i ++）{
		distance[i] = line[from][i];  //结点i到开始结点的路径长度赋值给数组distance 
		pred[i] = from;  //结点i的前一个结点赋值给数组pred 
		visited[i] = 0;  //初始状态下，结点均未被访问 
	}
	distance[from] = 0;  //将开始结点到开始结点的路径长度重新赋值为0 
	visited[from] = 1;   //开始结点已被访问 
	count = 1;      //记录循环次数 
	while（count < n-1）{
		min = INF;  //min记录结点到开始结点的最短路径长度 
		for（i = 1;i <= n;i ++）{
			if（distance[i] < min && !visited[i]）{  //如果结点到开始结点的路径长度小于无穷大且未被访问过 
				min = distance[i];
				nextnode = i;    //记录到开始结点最短路径长度的结点 
			}
		}
		visited[nextnode] = 1;
		for（i = 1;i <= n;i ++）{
			if（!visited[i]）{  //如果结点未被访问 
				if（min + line[nextnode][i] < distance[i]）{ 
				 //如果nextnode结点到开始结点的路径长度加上结点i到nextnode的路径长度小于结点i到开始结点的路径长度 
					distance[i] = min + line[nextnode][i];  //则更新结点i到开始结点的路径长度 
					pred[i] = nextnode;   //将结点i的前一个结点置为结点nextnode 
				}
			}
		}
		count ++;
	}
	
	char st;
	for（s = 1;s <= n;s ++）{
		if（s != from）{
			printf（“\n  到结点 %c 的距离 = %d“s + 64distance[s]）;  //将整型数字加64转换成字符的ASCII码，输出字符 
			printf（“\n  路径: %c“s + 64）;
			t = s;
			do{
				t = pred[t];
				printf（“  <-  %c“t + 64）;
			}
			

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       4357  2019-01-02 13:50  Dijkstra最短路径算法\Dijkstra最短路径算法（查看）.cpp

     文件      11898  2019-05-12 20:52  Dijkstra最短路径算法\邻接矩阵.docx

     目录          0  2019-07-09 11:27  Dijkstra最短路径算法

----------- ---------  ---------- -----  ----

                16255                    3