这是最短路径问题
首先有向赋权图得用邻接表来表示。
不知道邻接表是怎么建的，所以随便鼓捣了一下。。
#include
#include
#include
#define alloc(type) (type*)malloc(sizeof(type))
#define MAX_NUM 3.14E38
#define TRUE 1
#define FALSE 0
#define NODE_NUM 8
struct adj_list{
int index;
char name[10];
float len;
struct adj_list *next;
};
typedef struct adj_list Node;
//node[]为起始节点数组
int dijkstra(Node node[],int size,int first,float distance[],int previous[]){
//初始化数组
int *isused=new int[size];
for(int i=0;i
isused[i]=FALSE;
previous[i]=-1;
}
//初始起始节点和邻接节点间的距离
Node *pos=node[first].next;
if(pos==NULL)
return 0;
while(pos!=NULL){
distance[pos->index]=pos->len;
previous[pos->index]=first;
pos=pos->next;
}
//初始化开头节点
distance[first]=0;
isused[first]=TRUE;
int current=first;
//这里不是对所有的起始节点进行遍历
for(i=1;i
float temp=MAX_NUM;
for(int j=0;j
temp=distance[j];
}
}
if(current==first) break;
isused[current]=TRUE;
//更新distance[]列表
pos=node[current].next;
while(pos!=NULL){
if(isused[pos->index]==FALSE&&distance[pos->index]>distance[current]+pos->len){
distance[pos->index]=distance[current]+pos->len;
previous[pos->index]=current;
}
pos=pos->next;
}
}
return current;
}
//追踪线路
void printTrace(int lastindex,Node node[],int previous[]){
printf("最短路径为:");
if(lastindex==0)
printf("%s",node[0].name);
else{
int pos=lastindex;
while(true){
printf("%s ",node[pos].name);
if(pos==0) break;
pos=previous[pos];
}
printf("\n");
}
}
void generate(Node node[],int size){
//先输入顶点名字，然后按格式输入后面的链表节点
//格式为:name index len
//输入#结束链表节点的输入,转入其他顶点
for(int i=0;i
scanf("%s",node[i].name);
node[i].len=0.0;
node[i].index=i;
node[i].next=NULL;
Node *pos=&node[i];
char name[10];
int index=0;
float len=0.0;
while(true){
scanf("%s",name);
if(strcmp(name,"#")==0) break;
scanf("%d %f",&index,&len);
Node *no=alloc(Node);
strcpy(no->name,name);
no->index=index;
no->len=len;
no->next=NULL;
pos->next=no;
pos=pos->next;
}
}
}
void printnode(Node *node){
printf("(%d,%s,%g)",node->index,node->name,node->len);
}
void showtable(Node node[],int size){
for(int i=0;i
Node *pos=node[i].next;
while(pos!=NULL){
printf("->");
printnode(pos);
pos=pos->next;
}
printf("\n");
}
}
int main(){
Node node[NODE_NUM];
generate(node,NODE_NUM);
float distance[NODE_NUM];
int previous[NODE_NUM];
int lastindex=dijkstra(node,NODE_NUM,0,distance,previous);
printTrace(lastindex,node,previous);
return 0;
}
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ：24596024