以邻接表作存储结构实现求源点到其余各顶点的最短路径的Dijkstra算法
具体算法为：
//Dijkstra求单源最短路径
#include《stdio.h》
#define N 20 //图的顶点最多数
#define MAX 1000
#define MIN -1
typedef int ElemType;//图的顶点标识，这里为自然数
//图的结点结构
typedef struct ArcNode{
ElemType adjvex;//图的顶点 （该弧指向顶点的位置）
struct ArcNode *nextarc;//指向下一条弧的指针
int info//该弧权值
}ArcNode;
//表头结点表
typedef struct VertexNode{
ElemType data;
ArcNode *firstarc;
}VertexNode;
//图
typedef struct AdjList{
VertexNode vertex[N];
int vexnum;//图的顶点数
int arcnum;//弧数;
int kind;//图的种类（kind=1为有向图）
int dist[N];//图的路径长度
int path[N];//辅助数组
}AdjList;
//边
typedef struct{
int i;
int j;
int f;
}Side;
//邻接表法创建图
int CreateDAG(AdjList *L){
int i,j;
ArcNode *p=NULL;
//测试用例
Side S[N];
S.i=1;S.j=3;S.f=10;
S.i=1;S.j=5;S.f=30;
S.i=1;S.j=6;S.f=100;
S.i=2;S.j=3;S.f=5;
S.i=3;S.j=4;S.f=50;
S.i=4;S.j=6;S.f=10;
S.i=5;S.j=6;S.f=60;
S.i=5;S.j=4;S.f=20;
for(i=1;i《7;i++){
L-》vertex[i].data=i;
L-》dist[i]=MAX;//设为最大值，表示不可达
L-》path[i]=MIN;//设为最小值，表示尚未初始化
//L-》vertex[i].indegree=0;
L-》vertex[i].firstarc=NULL;
}
L-》kind=1;
L-》vexnum=6;
L-》arcnum=8;
for(i=0;i《8;i++){
p=(ArcNode *)malloc(sizeof(ArcNode));
p-》adjvex=S[i].j;
p-》info=S[i].f;
p-》nextarc=L-》vertex[(S[i].i)].firstarc;
L-》vertex[(S[i].i)].firstarc=p;
if(S[i].i==1){//初始顶点为1
L-》dist[(S[i].j)]=S[i].f;
//L-》path[(S[i].j)]=S[i].f;
}
// L-》vertex[(S[i].j)].indegree++;
}
return 1;
}
//输出邻接表存储
void PrintALGraph(AdjList *L){
ArcNode *p=NULL;
int i,k=0;
for(i=1;i《=L-》vexnum;i++){
k=L-》vertex[i].data;
printf(“V%d“,k);
// printf(“ 入度为%d 邻接点有 “,(L-》vertex[i].indegree));
p=L-》vertex[k].firstarc;
while(p!=NULL){
printf(“ -》%d“,p-》adjvex);
p=p-》nextarc;
}
printf(“\n“);
}
}
//Dijkstra求单源最短路径
void Dijkstra(AdjList *L){
int i=1,j,k=0;
Side s;
L-》path=0;
ArcNode *p=NULL;
while(k《10){
s.f=MAX;
for(i=1;i《=L-》vexnum;i++){
if(L-》path[i]!=MIN){
p=L-》vertex[i].firstarc;
if(p!=NULL){
while(p!=NULL){
if(s.f》p-》info&&L-》path[(p-》adjvex)]==MIN){
s.f=p-》info;
s.i=i;
s.j=p-》adjvex;
}
p=p-》nextarc;
}
}
}
}
if(s.f==MAX){
}else if(L-》dist[(s.j)]》L-》dist[(s.i)]+s.f){
L-》dist[(s.j)]=L-》dist[(s.i)]+s.f;
L-》path[(s.j)]=L-》dist[(s.j)];
}else{
L-》path[(s.j)]=L-》dist[(s.j)];
}
k++;
}
//输出
printf(“输出最短路径:\n“);
for(i=1;i《=L-》vexnum;i++){
if(L-》dist[i]==1000||i==1){
printf(“v1到v%d不存在最短路径\n“,i);
}else{
printf(“v1到v%d的最短路径是%d\n“,i,L-》dist[i]);
}
printf(“path is %d\n“,L-》path[i]);
}
}
int main(){
AdjList *L=(AdjList *)malloc(sizeof(AdjList));
if(CreateDAG(L)==1){
PrintALGraph(L);
Dijkstra(L);
}else{
printf(“创建失败\n“);
}
}
扩展资料：
要求带权有向图中某一顶点到其他各顶点的最短路径，常用Dijkstra算法，该算法基本思想是，先将图的顶点分为两个集合，一个为已求出最短路径的终点集合（开始为原点v1），另一个为还未求出最短路径的顶点集合（开始为除v1外的全部结点），然后按最短路径长度的递增顺序逐个将第二个集合的顶点加到第一组中。-最短路径
算法中使用dist数组，dist[i]表示目前已经找到、v1到vi的当前最短路径，否则为MAX；path数组，作为是否找到该点最短路径的标志，path[i]==MIN表示为未找到，否则为最短路径值。
常见的排序算法哪个效率最高
快速排序法。
Java的排序算法有哪些？
java的排序大的分类可以分为两种：内排序和外排序。在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。下面讲的排序都是属于内排序：
1.插入排序：直接插入排序、二分法插入排序、希尔排序。
2.选择排序：简单选择排序、堆排序。
3.交换排序：冒泡排序、快速排序。
4.归并排序。
5.基数排序。
java中的算法，一共有多少种，哪几种，怎么分类？
1、算法按实现方式分，有递归、迭代、平行、序列、过程、确定、不确定等。
2、算法按设计范型分，有分治、动态、贪心、线性、图论、简化等。
-算法
迪杰斯特拉算法的定义
Dijkstra算法是典型的算法。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。-最短路径
