#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?		min?=?INF;??//min記錄結點到開始結點的最短路徑長度?
		for（i?=?1;i?<=?n;i?++）{
			if（distance[i]?				min?=?distance[i];
				nextnode?=?i;????//記錄到開始結點最短路徑長度的結點?
			}
		}
		visited[nextnode]?=?1;
		for（i?=?1;i?<=?n;i?++）{
			if（!visited[i]）{??//如果結點未被訪問?
				if（min?+?line[nextnode][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