#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>
#define MaxVertex 10
#define INFINITY 65535
typedef int Vertex;
typedef struct AdjVNode *PtrToAdjVNode;
typedef struct GNode *PtrToGNode;
typedef struct ENode *PtrToENode;
typedef PtrToENode Edge;
typedef PtrToGNode LGraph;
struct ENode{
Vertex V1,V2;
int Weight;
};
struct AdjVNode{
Vertex Adj;
int Weight;
PtrToAdjVNode next;
};
typedef struct VNode{
PtrToAdjVNode FirstEdge;
}AdjList[MaxVertex];
struct GNode{
int Nv;
int Ne;
AdjList G;
};
LGraph CreateGraph(int VertexNum);
void InsertEdge(LGraph Graph,Edge E);
LGraph BuildGraph();
void Dijkstra(LGraph Graph,Vertex s,int collected[],int path[],int dist[]);
Vertex FindMinDist(LGraph Graph,int dist[]);
void Inititial(LGraph Graph,int Nv,int dist[]);
void Inititial(LGraph Graph,int Nv,int dist[]){
dist[Nv] = 0;
if(Graph->G[Nv].FirstEdge != NULL){
PtrToAdjVNode W = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
W = Graph->G[Nv].FirstEdge;
while(W != NULL){
dist[W->Adj] = W->Weight;
W = W->next;
}
}
}
Vertex FindMinDist(LGraph Graph,int dist[]){
int result = 0;
for(int i = 0;i < Graph->Nv;i++){
if(dist[i] > dist[i+1]){
result = i+1;
}
}
return result;
}
void Dijkstra(LGraph Graph,Vertex s,int collected[],int path[],int dist[]){
while(1){
Vertex V = FindMinDist(Graph,dist);
if(collected[V]){
break;
}
collected[V] = true;
if(Graph->G[V].FirstEdge != NULL){
PtrToAdjVNode W = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
W = Graph->G[V].FirstEdge;
while(W != NULL){
if(collected[W->Adj] == false){
if(dist[V] + W->Weight < dist[W->Adj]){
dist[W->Adj] = dist[V] + W->Weight;
path[W->Adj] = V;
}
}
W = W->next;
}
}
}
}
LGraph BuildGraph(){
LGraph Graph;
Vertex VertexNum;
printf("输入结点数:\n");
scanf("%d",&VertexNum);
Graph = CreateGraph(VertexNum);
printf("输入边数:\n");
scanf("%d",&Graph->Ne);
if(Graph->Ne != 0){
Edge E = (Edge)malloc(sizeof(struct ENode));
for(int i = 0;i < Graph->Nv;i++){
printf("输入要插入的两个结点以及权重:\n");
scanf("%d %d %d",&E->V1,&E->V2,&E->Weight);
InsertEdge(Graph,E);
}
}
return Graph;
}
void InsertEdge(LGraph Graph,Edge E){
PtrToAdjVNode NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
NewNode->Adj = E->V2;
NewNode->Weight = E->Weight;
NewNode->next = Graph->G[E->V1].FirstEdge;
Graph->G[E->V1].FirstEdge = NewNode;
NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
NewNode->Adj = E->V1;
NewNode->Weight = E->Weight;
NewNode->next = Graph->G[E->V2].FirstEdge;
Graph->G[E->V2].FirstEdge = NewNode;
}
LGraph CreateGraph(int VertexNum){
LGraph Graph = (LGraph)malloc(sizeof(struct GNode));
Graph->Nv = VertexNum;
Graph->Ne = 0;
for(int i = 0;i < Graph->Nv;i++){
Graph->G[i].FirstEdge = NULL;
}
return Graph;
}
int main () {
LGraph Graph = BuildGraph();
int dist[MaxVertex],collected[MaxVertex],path[MaxVertex];
int Nv;
for(int i = 0;i < Graph->Nv;i++){
dist[i] = INFINITY;
path[i] = -1;
collected[i] = false;
}
printf("输入要查找的单源最短路径的结点:\n");
scanf("%d",&Nv);
Inititial(Graph,Nv,dist);
Dijkstra(Graph,Nv,collected,path,dist);
for(int i = 0;i < Graph->Nv;i++){
if(Graph->G[i].FirstEdge != NULL){
PtrToAdjVNode p = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
p = Graph->G[i].FirstEdge;
while(p != NULL){
printf("%d",p->Adj);
p = p->next;
}
}
}
return 0;
}