問題描述
設計一個校園導游程序， 為來訪的客人提供信息查詢服務。
基本要求
（1）設計學校的校園平面圖，所含景點不少於10個，以圖中頂點表示校內各景點，存放景點名稱、代號、簡介等信息，以邊表示路徑，存放路徑長度等相關信息。
（2）為來訪客人提供圖中任意景點相關信息的查詢；
（3）為來訪客人提供從校門口到圖中任意景點的問路查詢；
算法思想
圖的表示采用最基本的鄰接矩陣的表示方式為，矩陣中A(i，j)值表示圖中點i與j之間權值，A（i，i）記為0，若沒有通路，記為infinity = 10000。忽略圖數據結構實現中不必要的細節，只提供最基本的功能，包括
[cpp]
int get_count();//得到圖中頂點數目；
void read(char* fname);
//從文件讀入並設置圖中頂點鄰接矩陣權值；
void write();//輸出臨界矩陣
void set_distances(Vertex source,
Weight distance[],Vertex ways[13][13]) const;
//得到由指定點到圖中各點最短路徑及值
單源最短路徑算法使用經典的Krim算法，首先初始化各點到源點的路徑為直接路徑，路徑值為源點到各頂點權值。之後選取路徑值最短的點（設為點k），並通過數組found[n]記錄每個點是否被找到的信息。選取一個點之後遍歷每個未找到的點，如果由源點經點k再到某點路徑值短於原記錄路徑值，則更新源點到其路徑為經過k，路徑值為源點到k路徑值加上k點到此點路徑值，再選取新路徑數組中路徑值最短的點；重復操作直至圖中所有的點都被找到。
[cpp]
template <class Weight, int graph_size>
void Digraph<Weight, graph_size>::set_distances(Vertex source,
Weight distance[],Vertex ways[13][13]) const
//輸出：數組array用以記錄源點source到每個點的最短路徑的值
// 二維數組ways用以記錄源點到每個點最短路徑所經過的點（即到達方式）
{
Vertex v, w;
bool found[graph_size]; // 存放找到的頂點
Vertex minways[graph_size];//存放當前找到的最短路徑的走法
//初始化各個頂點的信息
//每個頂點均為未找到，其最短路徑開始設為源點直接到此點的路徑，
//走法為源點直接到此點
for (v = 0; v < count; v++) {
found[v] = false;
distance[v] = adjacency[source][v];
ways[v][0]=0;
ways[v][1]=v;
minways[v]=infinity;
for(w=2;w<count;w++)
ways[v][w]=infinity;
}
//初始化源點，默認其為找到點，最短路徑為0
found[source] = true;
distance[source] = 0;
//最外層的循環每循環一次會找到一個頂點
for (int i = 0; i < count-1; i++) {
Weight min = infinity;
minways[0]=0;
//此循環判斷出當前還為被找到的頂點的最短路徑
//然後將此頂點設為已找到的點，其路徑設為min,其走法設為minways
//注意此處的關鍵是因為每次循環之後每個未找到點的“最短路徑”都相應新的集合做了改變
for (w = 0; w < count; w++){ if (!found[w])
if (distance[w] < min) {
v = w;
min = distance[w];
for(int j=0;j<count;j++)
minways[j]=ways[v][j];
}
}
found[v] = true;
//此循環用以修改未找到的點的最短路徑
//如果在找到的點中min+剛找到的點到此點的路徑小於原來的最短路徑，
//則改變最短路徑的值以及最短走法
//即剛新點後新的集合到點的路徑優化原來的路徑，則改變最短路徑的值
for (w = 0; w < count; w++) if (!found[w])
if (min + adjacency[v][w] < distance[w]){
distance[w] = min + adjacency[v][w];
int a=0;
while(minways[a]<infinity){
ways[w][a]=minways[a];
a++;
}
ways[w][a]=w;
}
}
}
單源最短路徑Krim算法流程
對於界面，因為功能並不復雜，我們使用Ezwin類庫。
實現思路很簡單，首先生成一個以虎溪校園平面為背景的窗口，右側為景點按鈕，點擊按鈕會生成景點介紹的窗口，相應的按鈕加載相應景點的介紹圖片，同時原窗口加載路徑圖。
最好的程序未必用最復雜的代碼，我們認為精簡優於繁雜，實現目的是王道！我們的校園景點查詢系統通篇代碼只有200行左右！
模塊劃分
1、 classDigraph 定義圖，其中單源最短路徑算法最為其成員函數實現
2、 主函數中實現圖的初始化及窗口的生成和事件的響應
數據結構
[cpp]
typedef int Vertex;
//infinity用以表示兩路之間沒有同路的值
const int infinity = 10000;
//創建Diagrah類表示圖
template <class Weight, int graph_size>
class Digraph {
public:
Digraph();
void read(char* fname);
void write();
int get_count();
void set_distances(Vertex source, Weight distance[],Vertex ways[13][13]) const;
protected:
int count; //圖中點的數目
Weight adjacency[graph_size][graph_size];//相鄰點之間的權值
};
測試情況
1、打開程序
開始界面：
2、查詢景點“圖書館”
顯示景點介紹窗口，並同時在原路徑圖顯示從北門到圖書館的最短路徑
3、查詢景點“第一教學樓”
景點介紹及最短路徑
4、各景點路徑詳細信息
項目演示
