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 typedef
int ElementType;
14 typedef
int Status;
15 typedef
int WeightType;
16 typedef
int Vertex;
17 typedef
char DataType;
18
19 typedef
struct ENode{
20 Vertex V1,V2;
//有向边<v1,V2>
21 WeightType Weight;
//权重
22 }ENode,*
PtrToENode ;
23
24 typedef PtrToENode Edge;
25
26 typedef
struct GNode{
27 int Nv;
//顶点数
28 int Ne;
//边数
29 WeightType G[MaxVerTexNum][MaxVerTexNum];
//邻接矩阵
30 DataType Data[MaxVerTexNum];
//save data of the Vertex;
31 }GNode,*
PtrToGNode;
32
33 typedef PtrToGNode MGraph;
34
35 MGraph CreateGraph(
int VertexNum);
//Create a Graph with VertexNum Vertex but without an ege;
36
37 void InsertEdge(MGraph Graph,Edge E);
38
39 MGraph BuildGraph();
40
41 Status IsEdge(MGraph Graph,Vertex V,Vertex W);
//检查<V,W>是不是图中的一条边，即W是不是V的邻接点
42
43 Status Floyd( MGraph Graph, WeightType D[][MaxVerTexNum], Vertex path[][MaxVerTexNum] );
44
45 int main(
int argc,
char**
argv)
46 {
47 MGraph Graph;
48 Graph=
BuildGraph();
49 int D[MaxVerTexNum][MaxVerTexNum];
50 int path[MaxVerTexNum][MaxVerTexNum];
51 int i,j;
52 int count=
0;
53 Floyd(Graph,D,path);
54
55 for(i=
0;i<Graph->Nv;i++
)
56 for(j=
0;j<Graph->Nv;j++
)
57 {
58 count++
;
59 printf(
"%d ",D[i][j]);
60 if(count%Graph->Nv==
0)
61 printf(
"\n");
62 }
63 count=
0;
64 for(i=
0;i<Graph->Nv;i++
)
65 for(j=
0;j<Graph->Nv;j++
)
66 {
67 count++
;
68 if(path[i][j]==-
1)
69 printf(
"%d ",path[i][j]);
70 else
71 printf(
" %d ",path[i][j]);
72
73 if(count%Graph->Nv==
0)
74 printf(
"\n");
75 }
76 return 0;
77 }
78
79 MGraph CreateGraph(
int VertexNum){
80 Vertex V,W;
81 MGraph Graph;
82 Graph=(MGraph)
malloc(
sizeof(GNode));
83 Graph->Nv=
VertexNum;
84 Graph->Ne=
0;
//
85 for(V=
0;V<Graph->Nv;V++
)
86 for(W=
0;W<Graph->Nv;W++
)
87 Graph->G[V][W]=
INFINITY;
88 return Graph;
89 }
90
91 void InsertEdge(MGraph Graph,Edge E){
92 Graph->G[E->V1][E->V2]=E->
Weight;
93 //若是无向图还要插入
94 Graph->G[E->V2][E->V1]=E->
Weight;
95 }
96
97 MGraph BuildGraph(){
98 MGraph Graph;
99 Edge E;
100 Vertex V;
101 int Nv,i;
102 printf(
"输入结点的个数\n");
103 scanf(
"%d",&Nv);
//the number of vertex
104 Graph=CreateGraph(Nv);
//initate graph with Nv vertexs !!return 回去要赋值给Graph；
105 //getchar();
106 printf(
"输入弧的个数\n");
107 scanf(
"%d",&(Graph->Ne));
//read the number of ege
108 if(Graph->Ne!=
0)
109 {
110 E=(Edge)
malloc(
sizeof(ENode));
111 for(i=
0;i<Graph->Ne;i++
){
112 // getchar();
113 printf(
"输入弧的信息V1 V2 Weight\n");
114 scanf(
"%d %d %d",&(E->V1),&(E->V2),&(E->
Weight));
115 InsertEdge(Graph,E);
116 }
117 }
118 // for(V=0;V<Graph->Nv;V++)
119 // scanf("%c",&(Graph->Data[V]));
120 return Graph;
121
122 }
123 Status IsEdge(MGraph Graph,Vertex V,Vertex W){
124 return Graph->G[V][W]<INFINITY?
TRUE:FALSE;
125 }
126
127
128 Status Floyd( MGraph Graph, WeightType D[][MaxVerTexNum], Vertex path[][MaxVerTexNum] ){
129 Vertex i, j, k;
130 //上面默认没有赋值的便都是INFINITY,因此要重新置零
131 for(i=
0;i<Graph->Nv;i++
)
132 for(j=
0;j<Graph->Nv;j++
)
133 if(i==
j)
134 Graph->G[i][j]=
0;
135
136
137
138 for ( i=
0; i<Graph->Nv; i++
)
139 for( j=
0; j<Graph->Nv; j++
) {
140 D[i][j] = Graph->
G[i][j];
141 path[i][j] = -
1;
142 }
143
144 for( k=
0; k<Graph->Nv; k++
)
145 for( i=
0; i<Graph->Nv; i++
)
146 for( j=
0; j<Graph->Nv; j++
)
147 if( D[i][k] + D[k][j] <
D[i][j] ) {
148 D[i][j] = D[i][k] +
D[k][j];
149 if ( i==j && D[i][j]<
0 )
/* 若发现负值圈 */
150 return FALSE;
/* 不能正确解决，返回错误标记 */
151 path[i][j] =
k;
152 }
153 return OK;
154
155
156
157 }
转载于:https://www.cnblogs.com/lovecodepql/p/7781046.html
