想法是这样的：
1. 最开始要建立4个list，分别存储
a. 所有的Vertex: allVertex[]
b. 一个空的Vertex list: emptyVertex[]
c. 一个前缀表 previous list(用来回溯路径用): previous[]
d. 一个表示最短距离的表(就是表示某个点与0点的最短距离)：
前两个list是用来辅助操作的，后2个表则是输出，通过后2个表我们能得到想要的一切结果。
因此我们的任务其实就是，最终把c。d两个表填充完毕即可。
2. 我们要做一个循环，循环次数为VertexMax次，因为如果是连通图，每次循环都能处理一个Vertex。
3. 第一次循环前我们把start这个vertex从allVertex表，移动到emptyVertex表。
4. 这样我们就需要遍历，与empty表所有vertex关联的每一条line。找出这些line中最短的一条。
5. 找到最短的这条line之后，更新一下previous表，previous[line->end] = start; 然后更新一下distances表, (distances[line->end]) 同 (distances[start] + line->weight)取最小值
6. 然后,line->end作为新的start，重新进入循环。。重复3-5步即可。
[cpp]
#include
using namespace std;
const int MAX_VERTEX = 5;//图的顶点数
const int MAX_INT = 0x7fffffff;//4字节的整数
const int MIN_INT = 0xffffffff;//4字节的整数
enum Kind{NG, DG};//无向图，有向图
Kind k = NG;//图的种类
int graph[MAX_VERTEX][MAX_VERTEX];//图
int emptyVertex[MAX_VERTEX];//空的Vertex集合
int allVertex[MAX_VERTEX];//当前Vertex集合
int previous[MAX_VERTEX];//前缀
int distances[MAX_VERTEX];//distance
void printGraph(){//打印图
cout<<"-----------begin-------------"<
for(int i = 0; i < MAX_VERTEX; i++){
for(int j = 0; j < MAX_VERTEX; j++){
if(graph[i][j] < MAX_INT){
cout<
}else{
cout<<"∞\t";
}
}
cout<<"\n\v";
}
cout<<"-----------end-------------"<
}
void printArr(int *arr, int len){//打印数组
for(int i = 0; i < len; i++){
if(arr[i] >= MAX_INT){
cout<<"∞\t";
}else{
cout<
}
}
cout<
}
void printSituation(){//打印整个结构的各个数据部分。
cout<<"[[======================================"<
//cout<<"graph:\n";
//printGraph();
cout<<"allVertex:\n";
printArr(allVertex, MAX_VERTEX);
cout<<"emptyVertex:\n";
printArr(emptyVertex, MAX_VERTEX);
cout<<"previous:\n";
printArr(previous, MAX_VERTEX);
cout<<"distances:\n";
printArr(distances, MAX_VERTEX);
cout<<"======================================]]"<
}
void init(){//初始化
for(int i = 0; i < MAX_VERTEX; i++){
emptyVertex[i] = MAX_INT;
allVertex[i] = i;
previous[i] = MAX_INT;
distances[i] = MAX_INT;
for(int j = 0; j < MAX_VERTEX; j++){
graph[i][j] = MAX_INT;
}
}
distances[0] = 0;
}
void addLine(int start, int end, int weight){//增加一条line
if(start >= MAX_VERTEX || end >= MAX_VERTEX) return;
graph[start][end] = weight;
if(k == NG){
graph[end][start] = weight;
}
}
void rmLine(int start, int end){//移除一条line
if(start >= MAX_VERTEX || end >= MAX_VERTEX) return;
graph[start][end] = MAX_INT;
if(k == NG){
graph[end][start] = MAX_INT;
}
}
void dijkstra(){
int start = 0;
int emptyI = 0;//emptyVertex数组的下标
int numHandled = 0;//每次循环都能处理一个vertex，因此需要循环MAX_VERTEX次。
while(numHandled < MAX_VERTEX){
//1. 把start从allVertex中取出，放入emptyVertex中
emptyVertex[emptyI++] = allVertex[start];
allVertex[start] = MAX_INT;
//2. 找出 已经加入到 empty中的所有点上 的所有的line, 选出其中最短的一条，其end点作为下一次访问的起始点。
//3. 根据这些line重新计算distances, 更新distances表--同时更新前缀表，前缀表是随着distances表变化的。
int shortestWeight = MAX_INT;
int shortestEnd = MIN_INT;
for(int j = 0; j < MAX_VERTEX; j++){
int currentStart = emptyVertex[j];
if(currentStart < MAX_INT){//每一个在empty中的vertex都必须参加比较。在所有的这些vertex中关联的line中选一条 end 值不在empty中的最短的line。
for(int i = 0; i < MAX_VERTEX; i++){//i值表示 (currentStart -> i) 这条 line 的 end值
if(graph[currentStart][i] >= MAX_INT) {//如果这条line不存在，搜索下一条
continue;
}
else{