西工大NOJ数据结构理论——022.Dijkstra算法（严7.42）

我直到最近才意识到，为什么我开学前几周有时间来做这个博客了，是因为我选的大物实验是从第9周开始的，而大家很多人选的都是第3到第8周，所以我之前就会有很多的空闲时间来做这个事情，而不是什么我时间效率利用高。自从第9周开始，我的时间就明显不够用了，因为这个大物实验实在太费时间了，所以就导致我最近更新这么慢。

回到这道题，我认为的两大法宝是：

1.足量的注释；

2.逐步的调试。

当然，这个代码还有很多的不足，现在又要考试了，我实在没心思再静下心来优化它了，等暑假再优化叭（这大概率又是一个必会倒的 flag）

#include
#include
#define MAX_VERTEX_NUM 120
#define YES 1
#define NO 0
typedef struct Dist{ //D数组 
	int adjvex; //最终要到达的顶点 
	int length; //当前路径的长度 
	int done; //如果确定了当前路径就是最短路径，那么done=1 
}Path;

typedef struct ArcNode{ //弧 
	int adjvex; //该弧所指向的顶点的位置 
	struct ArcNode *nextarc; //指向下一条弧的指针 
	int length; //该弧的路径长度 
}ArcNode;

typedef struct VNode{ //顶点 
	int data; //顶点信息 
	ArcNode *firstarc; //指向第一条依附该顶点的弧的指针 
}VNode;

typedef struct ALGraph{ //图 
	VNode vertices[MAX_VERTEX_NUM]; //图的各个顶点 
	int vexnum,arcnum; //图的当前结点数和弧数 
}ALGraph;

void graph_initialize(ALGraph* graph){ //图的初始化 
	graph->vexnum=0;
	graph->arcnum=0;
	for(int i=0;ivertices[i].data=0;
		graph->vertices[i].firstarc=NULL;
	}
}

void arcnode_initialize(ArcNode* arcnode){ //弧结点的初始化 
	arcnode->adjvex=0;
	arcnode->nextarc=NULL;
}

ArcNode* arcnode_create(){ //弧结点的创建 
	ArcNode *arcnode=(ArcNode*)malloc(sizeof(ArcNode));
	arcnode_initialize(arcnode);
	return arcnode;
}

ALGraph* graph_create(){ //图的创建 
	ALGraph* graph=(ALGraph*)malloc(sizeof(ALGraph));
	graph_initialize(graph);
	int n,m; //n是顶点数，m是边数 
	scanf("%d %d",&n,&m);
	graph->vexnum=n;
	graph->arcnum=m; 
	for(int i=1;i<=graph->vexnum;i++){//读入顶点信息 
		graph->vertices[i].data=i;
		graph->vertices[i].firstarc=NULL;
	}
	for(int j=0;jarcnum;j++){ //读入弧信息 
		int a,b,length;
		//a是弧尾，b是弧头，length是路径长度 
		scanf("%d %d %d",&a,&b,&length);
		//下面用创建一个弧结点，并且完善这个结点的信息： 
		ArcNode *arcnode=arcnode_create();
		arcnode->adjvex=b;
		arcnode->length=length; 
		//下面找到弧要插入的位置（尾插法） 
		int i=0;
		while(ivexnum){
			if(graph->vertices[i].data==a) break;
			i++; 
		}
		ArcNode *temp=graph->vertices[i].firstarc;
		//如果插入的位置很尴尬，恰好是第一个，那我们就得把它单独拉出来做成特殊情况。 
		if(temp==NULL) graph->vertices[i].firstarc=arcnode;
		//但如果它不是第一个，那我们就把它当成普遍情况来对待 
		else{
			while(temp->nextarc) temp=temp->nextarc;
			//找到要插入的位置后，插入进去 
			temp->nextarc=arcnode;
		}
	}
	return graph;
}

int Dijkstra(ALGraph* graph){
	//第一大步，创建一个D数组，用来记录最短路径 
			//因为第0个位置是不用的，而第1个位置是从原点到原点，也是不用的 
			//所以如果有6个顶点，就得要给它分配7个位置 
	Path D[graph->vexnum+1];
	//第二大步，我们对D数组进行初始化操作 
		//第一步，默认从原点到不了任何一个顶点: 
	for(int i=2;i<=graph->vexnum;i++){
		D[i].adjvex=i;
		D[i].length=10000;
		//在这里，将D[i].length设为10000，就表示路径长度为无穷大 
		D[i].done=NO;
	}
		//最终，通过这个循环，系统认为，从1到不了2，3，4，5，6 
		//第二步，根据邻接表，确定从原点能到达哪些顶点： 
	ArcNode *temp=graph->vertices[1].firstarc;
	while(temp){
		D[temp->adjvex].length=temp->length;
		temp=temp->nextarc;
	}
		//最终，通过这个while循环，我们确定了从1能到达哪些顶点 
	//第三大步，假如共有1，2，3，4，5，6这6个顶点，那么分5次，每次找出从1到单顶点的最短路径 
	for(int times=1;times<=5;times++){
		//第一步，在数组D中找到最小的那一个(也就是路径最短) 
		//这里随便给个min_vex的初值，要不然处理太麻烦。 
		int min_vex=2;
		while(min_vex<=graph->vexnum){
			if(D[min_vex].done==YES){
				min_vex++;
			}
			else{
				break;
			}
		}
		for(int i=2;i<=graph->vexnum;i++){
			if(D[i].done==YES){
				continue;
				//如果从原点1到i的最短路径已经找到了，那就不用看它了 
			}
			if(D[i].lengthvexnum;i++){
			if(D[i].done==YES) continue;
			//如果从原点1到min_vex，再从min_vex到i的路径已经确定为最短了，那么就不看它了 
			ArcNode* temp=graph->vertices[min_vex].firstarc;
			int flag=0;
			while(temp){
				if(temp->adjvex==i){
					flag=1; break;
				}
				temp=temp->nextarc;
			}
			if(flag==0) continue;
			//如果没有从原点1到min_vex，再从min_vex到i的路径的原因，是从min_vex到不了i，那么也不看它了 
			//相反，如果路径存在，那我们可就要好好看看了： 
			else if(flag==1){
				//怎么个好好看法呢？不难，就是看从原点1到min_vex，再从min_vex到i，是不是能比D[i]更短：  
				//如果能更短，那何乐而不为呢？二话不说就把D[i]更新掉。 
				if(D[min_vex].length+temp->lengthlength;
				} 
			}
		}
	}
	//第四大步，根据D[]数组，输出不可达的路径 
	for(int i=2;i<=graph->vexnum;i++){
		if(D[i].length==10000){
			printf("%d %d -1n",1,i);
		}
	}
}

int main(){
	ALGraph* graph=graph_create();
	//首先，用这个函数处理掉所有的input 
	Dijkstra(graph);
	//然后，用这个函数得到从1到2、3、4、5、6......的最短路径output 
	return 0;
}

mmp说我字数不够，那我把几个函数拿下来凑个字数叭

int Dijkstra(ALGraph* graph){
    //第一大步，创建一个D数组，用来记录最短路径 
            //因为第0个位置是不用的，而第1个位置是从原点到原点，也是不用的 
            //所以如果有6个顶点，就得要给它分配7个位置 
    Path D[graph->vexnum+1];
    //第二大步，我们对D数组进行初始化操作 
        //第一步，默认从原点到不了任何一个顶点: 
    for(int i=2;i<=graph->vexnum;i++){
        D[i].adjvex=i;
        D[i].length=10000;
        //在这里，将D[i].length设为10000，就表示路径长度为无穷大 
        D[i].done=NO;
    }
        //最终，通过这个循环，系统认为，从1到不了2，3，4，5，6 
        //第二步，根据邻接表，确定从原点能到达哪些顶点： 
    ArcNode *temp=graph->vertices[1].firstarc;
    while(temp){
        D[temp->adjvex].length=temp->length;
        temp=temp->nextarc;
    }
        //最终，通过这个while循环，我们确定了从1能到达哪些顶点 
    //第三大步，假如共有1，2，3，4，5，6这6个顶点，那么分5次，每次找出从1到单顶点的最短路径 
    for(int times=1;times<=5;times++){
        //第一步，在数组D中找到最小的那一个(也就是路径最短) 
        //这里随便给个min_vex的初值，要不然处理太麻烦。 
        int min_vex=2;
        while(min_vex<=graph->vexnum){
            if(D[min_vex].done==YES){
                min_vex++;
            }
            else{
                break;
            }
        }
        for(int i=2;i<=graph->vexnum;i++){
            if(D[i].done==YES){
                continue;
                //如果从原点1到i的最短路径已经找到了，那就不用看它了 
            }
            if(D[i].length         }
        D[min_vex].done=YES;
        //然后从小到大输出最短路径： 
        if(D[min_vex].length!=10000){
            printf("%d %d %dn",1,min_vex,D[min_vex].length);
        }
        //最终，通过这个循环，确定了从1到单个顶点的最短路径，我们把它标记为done=YES,这样以后就不用再去看它了 
        //第二步，我们看一看从原点1到min_vex,再从min_vex到2,3,4,5,6，是不是能更短 
        for(int i=2;i<=graph->vexnum;i++){
            if(D[i].done==YES) continue;
            //如果从原点1到min_vex，再从min_vex到i的路径已经确定为最短了，那么就不看它了 
            ArcNode* temp=graph->vertices[min_vex].firstarc;
            int flag=0;
            while(temp){
                if(temp->adjvex==i){
                    flag=1; break;
                }
                temp=temp->nextarc;
            }
            if(flag==0) continue;
            //如果没有从原点1到min_vex，再从min_vex到i的路径的原因，是从min_vex到不了i，那么也不看它了 
            //相反，如果路径存在，那我们可就要好好看看了： 
            else if(flag==1){
                //怎么个好好看法呢？不难，就是看从原点1到min_vex，再从min_vex到i，是不是能比D[i]更短：  
                //如果能更短，那何乐而不为呢？二话不说就把D[i]更新掉。 
                if(D[min_vex].length+temp->length
                    D[i].length=D[min_vex].length+temp->length;
                } 
            }
        }
    }
    //第四大步，根据D[]数组，输出不可达的路径 
    for(int i=2;i<=graph->vexnum;i++){
        if(D[i].length==10000){
            printf("%d %d -1n",1,i);
        }
    }
}