1 #include<stdio.h>
2 #include<stdlib.h>
3
4 #define OK 1
5 #define NO 0
6 #define TRUE 1
7 #define FALSE 0
8 #define ERROR -1
9
10 #define MaxVerTexNum 100
11 #define INFINITY 65535
12
13
14
15
16 typedef
int ElementType;
17 typedef
int Status;
18 typedef
int WeightType;
19 typedef
int Vertex;
20 typedef
char DataType;
21
22 typedef
int Position;
23 typedef
struct QNode{
24 ElementType *
Data;
25 Position Front, Rear;
26 int MaxSize;
27 }QNode,*
Queue;
28
29
30
31 Status Visited[MaxVerTexNum];
32
33 typedef
struct ENode{
34 Vertex V1,V2;
//有向边<v1,V2>
35 WeightType Weight;
//权重
36 }ENode,*
PtrToENode ;
37
38 typedef PtrToENode Edge;
39
40 Status IsFull( Queue Q );
41
42 typedef
struct GNode{
43 int Nv;
//顶点数
44 int Ne;
//边数
45 WeightType G[MaxVerTexNum][MaxVerTexNum];
//邻接矩阵
46 DataType Data[MaxVerTexNum];
//save data of the Vertex;
47 }GNode,*
PtrToGNode;
48
49 typedef PtrToGNode MGraph;
50
51 MGraph CreateGraph(
int VertexNum);
//Create a Graph with VertexNum Vertex but without an ege;
52
53 void InsertEdge(MGraph Graph,Edge E);
54
55 MGraph BuildGraph();
56
57 Status IsEdge(MGraph Graph,Vertex V,Vertex W);
//检查<V,W>是不是图中的一条边，即W是不是V的邻接点
58
59
60
61 Vertex FindMinDist(MGraph Graph,
int dist[],
int collected[]);
62
63 Status Dijkstra(MGraph Graph,
int dist[],
int path[],Vertex S);
64
65 int main(
int argc,
char**
argv)
66 {
67 MGraph Graph;
68 Graph=
BuildGraph();
69 int dist[MaxVerTexNum];
70 int path[MaxVerTexNum];
71 int S=
1;
72 int i,j;
73 int sum;
74 for(i=
0;i<MaxVerTexNum;i++
)
75 {
76 dist[i]=
INFINITY;
77 path[i]=-
1;
78 }
79
80
81
82 Dijkstra(Graph,dist,path,S);
83 for(j=
0;j<Graph->Nv;j++){
//出现死循环要多调试
84 i=
j;
85 sum=
0;
86 while(i!=-
1){
87
88 printf(
"%d",i);
89 i=
path[i];
90 if(i!=-
1){
91 printf(
"<--");
92 sum++
;
93 }
94
95 }
96 printf(
"\n");
97 printf(
"从%d到%d的无权图最短路径为%d\n",S,j,sum);
98 printf(
"\n");
99 }
100
101 return 0;
102 }
103
104 MGraph CreateGraph(
int VertexNum){
105 Vertex V,W;
106 MGraph Graph;
107 Graph=(MGraph)
malloc(
sizeof(GNode));
108 Graph->Nv=
VertexNum;
109 Graph->Ne=
0;
//
110 for(V=
0;V<Graph->Nv;V++
)
111 for(W=
0;W<Graph->Nv;W++
)
112 Graph->G[V][W]=
INFINITY;
113 return Graph;
114 }
115
116 void InsertEdge(MGraph Graph,Edge E){
117 Graph->G[E->V1][E->V2]=E->
Weight;
118 //若是无向图还要插入
119 Graph->G[E->V2][E->V1]=E->
Weight;
120 }
121
122 MGraph BuildGraph(){
123 MGraph Graph;
124 Edge E;
125 Vertex V;
126 int Nv,i;
127 printf(
"输入结点的个数\n");
128 scanf(
"%d",&Nv);
//the number of vertex
129 Graph=CreateGraph(Nv);
//initate graph with Nv vertexs !!return 回去要赋值给Graph；
130 //getchar();
131 printf(
"输入弧的个数\n");
132 scanf(
"%d",&(Graph->Ne));
//read the number of ege
133 if(Graph->Ne!=
0)
134 {
135 E=(Edge)
malloc(
sizeof(ENode));
136 for(i=
0;i<Graph->Ne;i++
){
137 // getchar();
138 printf(
"输入弧的信息V1 V2 Weight\n");
139 scanf(
"%d %d %d",&(E->V1),&(E->V2),&(E->
Weight));
140 InsertEdge(Graph,E);
141 }
142 }
143 // for(V=0;V<Graph->Nv;V++)
144 // scanf("%c",&(Graph->Data[V]));
145 return Graph;
146
147 }
148 Status IsEdge(MGraph Graph,Vertex V,Vertex W){
149 return Graph->G[V][W]<INFINITY?
TRUE:FALSE;
150 }
151
152
153 Vertex FindMinDist(MGraph Graph,
int dist[],
int collected[]){
//返回未被收录顶点中dist最小者
154 Vertex MinV,V;
//其中MinV用来标记返回的顶点序号，V就是作为顶点的序号
155 int MinDist=INFINITY;
//MinDist用来找到所有未被访问的顶点中Dist最小的那个
156 for(V=
0;V<Graph->Nv;V++
)
157 {
158 if(collected[V]==FALSE&&dist[V]<
MinDist){
159 /* 若V未被收录，且dist[V]更小 */
160 MinDist=dist[V];
//更新最小距离
161 MinV=
V;
162 }
163 }
164 if(MinDist<INFINITY)
//找到最小的dist
165 return MinV;
166 else
167 return ERROR;
168
169 }
170
171 Status Dijkstra(MGraph Graph,
int dist[],
int path[],Vertex S){
172 int collected[MaxVerTexNum];
173 Vertex V,W;
174 //初始化，默认邻接矩阵中不存在的边用INFINITY表示
175 /*对dist的初始化非常的重要，因为第一个点必须从S点开始，因此要把它的dist设置成0，但默认值是INFINITY所以要改正
176 在初始化的时候也一定要满足其path[S]=-1的条件 */
177 for(V=
0;V<Graph->Nv;V++
)
178 {
179 dist[V]=Graph->G[S][V];
//初始化为邻接矩阵的大小
180 if(S==
V)
181 dist[V]=
0;
//！！！！
182 if(dist[V]<INFINITY&&dist[V]!=
0)
//！！！！
183 path[V]=S;
//标记路线的前一个值为S
184 else
185 path[V]=-
1;
//前一个结点不存在
186 collected[V]=FALSE;
//初始化标记矩阵
187 }
188 while(
1){
189 //V=为被收录的顶点中dist最小的那个
190 V=
FindMinDist(Graph,dist,collected);
191 if(V==
ERROR)
192 break;
//如果这样的点不存在，表明剩下的点没有与已知的点连接或者所有的点都已经被连接标记
193 collected[V]=TRUE;
//收录V
194 for(W=
0;W<Graph->Nv;W++)
//对图中每个顶点
195 if(collected[W]==FALSE&&Graph->G[V][W]<
INFINITY){
196 if(Graph->G[V][W]<
0)
//若有负边
197 return ERROR;
198 if(dist[V]+Graph->G[V][W]<
dist[W])
199 dist[W]=dist[V]+Graph->
G[V][W];
200 path[W]=
V;
201 }
202
203
204
205
206 }
207
208
209 }
转载于:https://www.cnblogs.com/lovecodepql/p/7780882.html
相关资源：图的邻接矩阵，给定一个图，输出它的邻接矩阵
