資源簡介
本程序使用C語言實現了Dijkstra算法。程序中，定義好鄰接矩陣，可以計算出任一節點到其他所有節點的最短路徑，并打印路徑與長度。其中對最短路徑的存儲是依據所得到的生成樹，可以減少內存空間占用。
代碼片段和文件信息
//給定鄰接矩陣，采用Dijkstra算法計算某一節點到其他所有節點的最短路徑
#include
#define?uchar?unsigned?char
#define?N?6 //節點數目
int?adj[N][N]={ //鄰接矩陣，adj[i][j]表示節點i至節點j的直連路徑長度，其中99表示i與j不直連
{019949999}?
{10399199}
{99309912}
{499990199}
{9911104}
{999929940}};
//節點source至其他節點的最短路徑表
struct?shpt
{
char?source; //源節點
struct //這些路徑剛好構成一個生成樹，有N-1條鏈路，為方便處理，加上一條從source到source的長度為0的鏈路
{
char?start; //鏈路起點
char?end; //鏈路終點
}link[N];
int?len[N]; //source到所有節點的最短路徑長度
}xto;
void?main（）
{
int?ij;
char?min_nmin_vsour; //min_n:最小值對應節點，min_v:最小值，sour:源節點
int dis_tmp[N]; //當前最短路徑值
char?trans[N]; //以誰為中轉
char?decided[N]={0}; //節點i的最短路徑已確定
//初始化
printf（“輸入起始節點：“）;
scanf（“%d“&sour）;sour-- ?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2015-08-09?01:06??Dijkstra算法\
?????目錄???????????0??2015-08-09?01:05??Dijkstra算法\Debug\
?????文件??????184398??2015-08-09?01:05??Dijkstra算法\Debug\Dijkstra算法.exe
?????文件??????182244??2015-08-09?01:05??Dijkstra算法\Debug\Dijkstra算法.ilk
?????文件????????4544??2015-08-09?01:05??Dijkstra算法\Debug\Dijkstra算法.obj
?????文件??????203800??2015-08-09?01:05??Dijkstra算法\Debug\Dijkstra算法.pch
?????文件??????361472??2015-08-09?01:05??Dijkstra算法\Debug\Dijkstra算法.pdb
?????文件???????33792??2015-08-09?01:05??Dijkstra算法\Debug\vc60.idb
?????文件???????45056??2015-08-09?01:05??Dijkstra算法\Debug\vc60.pdb
?????文件????????2313??2015-08-09?00:54??Dijkstra算法\Dijkstra算法.cpp
?????文件????????3475??2015-08-09?01:04??Dijkstra算法\Dijkstra算法.dsp
?????文件?????????532??2015-08-09?01:04??Dijkstra算法\Dijkstra算法.dsw
?????文件???????41984??2015-08-09?01:06??Dijkstra算法\Dijkstra算法.ncb
?????文件???????48640??2015-08-09?01:06??Dijkstra算法\Dijkstra算法.opt
?????文件?????????780??2015-08-09?01:05??Dijkstra算法\Dijkstra算法.plg
評論
共有 條評論