#include<stdio.h>
#include<stdlib.h>
#define intmax 32767
typedef struct node{
int data;
int w;
struct node *next;
}Node;
typedef struct adjnode{
char ch[10];
Node *firstarc;
}Adjnode;
typedef struct f{
int *p;
}Path;
locate(Adjnode *adj,int n,char *s)
{
int i;
for(i=0;i<n;i++)
if(strcmp(adj[i].ch,s)==0)return i;
return -1;
}
createadj(Adjnode **adj,int n,int e)
{char s[10],t[10],w[10]; int i,j,k;
Node *p,*q;
printf("输入各顶点的字符串.\n");
for(i=0;i<n;i++)
{ gets(s);
strcpy((*adj)[i].ch,s);
(*adj)[i].firstarc=NULL;
}
printf("请输入各条边.\n"); /*如v1回车v2回车表明有v1到v2的边*/
for(i=1;i<=e;i++)
{
gets(s);
gets(t);
gets(w);
j=locate(*adj,n,s);
k=locate(*adj,n,t);
if(k>=0 && j>=0 && j!=k){
p=(Node *)malloc(sizeof(Node));
p->data=k;p->w=atoi(w);
p->next=(*adj)[j].firstarc;
(*adj)[j].firstarc=p;
}
else
printf("边的顶点输入不正确!\n");
}
}
minvetex(int dist[],int n,int visited[],int v)
{
int i=0,j;int vetex=-1;
while(i<n && (visited[i]==1 || i==v))i++;
if(i<n)vetex=i;
for(j=i+1;j<n;j++)
if(visited[i]!=1 && i!=v && dist[vetex]>dist[j])vetex=j;
return vetex;
}
minpath(Adjnode *adj,int n,int v)
{
int *dist,i,j,k,vetex;Path *path;Node *p;
int *visited;
dist=(int *)malloc(sizeof(int)*(n-1));
path=(Path *)malloc(sizeof(Path)*(n-1));
visited=(int *)malloc(sizeof(int)*n);
for(i=0;i<n;i++)
visited[i]=0;
for(i=0;i<n;i++)
{ dist[i]=intmax;
path[i].p=(int *)malloc(sizeof(int)*(n+1));
path[i].p[0]=0;
}
dist[v]=0;
p=adj[v].firstarc;
while(p){
dist[p->data]=p->w;path[p->data].p[0]=2;
path[p->data].p[1]=v;
path[p->data].p[2]=p->data;
p=p->next;
}
path[v].p[0]=2;
path[v].p[1]=v;path[v].p[2]=v;
for(i=1;i<n;i++)
{
vetex=minvetex(dist,n,visited,v);
if(vetex>=0){
visited[vetex]=1;
for(j=0;j<n;j++)
if(visited[j]!=1 && j!=v)
{
p=adj[vetex].firstarc;
while(p ){
if(p->data==j)break;
p=p->next;
}
if(p && dist[j]>dist[vetex]+p->w)
{
dist[j]=dist[vetex]+p->w;
path[j].p[0]=path[vetex].p[0]+1;
for(k=1;k<=path[vetex].p[0];k++)
path[j].p[k]=path[vetex].p[k];
path[j].p[k]=j;
}
}
}/*if*/
}/*for*/
for(i=0;i<n;i++)
{
printf("the distance of %s-->%s=%d\n",adj[v].ch,adj[i].ch,dist[i]);
printf("the path of %s-->%s=",adj[v].ch,adj[i].ch);
for(j=1;j<=path[i].p[0];j++)
printf("%s ",adj[path[i].p[j]].ch);
printf("\n");
}
}
main()
{
int n,e,i;
Adjnode *adj;char s[10];
printf("输入无向图的顶点数和边数.\n");
do
scanf("%d%d",&n,&e);
while(n<=0 || e<=0);
getchar();
adj=(Adjnode *)malloc(sizeof(Adjnode)*n);
createadj(&adj,n,e);
printf("请输入某个出发的顶点:\n");
gets(s);
i=locate(adj,n,s);
if(i>=0 && i<n)
minpath(adj,n,i);
}
shujujiegou.rar_shujujiegou
版权申诉
140 浏览量
2022-09-24
00:02:28
上传
评论
收藏 28KB RAR 举报
JaniceLu
- 粉丝: 82
- 资源: 1万+
最新资源
- meta-llama-3-8b-instruct 的 model-00004-of-00004.safetensors
- IMG_0006.CR2.cr2
- 幸运红包娱乐微信小程序源码 多玩法安装简单
- packagecom5_QQ浏览器压缩包.zip
- MY3-3WHY-可以刷萤石H6C-V100-2C3WF
- 深度解析木马隐藏技术:核心原理与VMware网络实验指南
- pbootcms百度智能小程序插件
- 指令调度和延迟分支学习资料.rar
- HTML5小游戏【飞得更高跳跃游戏feidegenggao】游戏源码分享下载 - feidegenggao.zip
- 第一讲:单片机STC89C52+RA8889驱动控制彩屏(源码公开)
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈