用c语言建立邻接矩阵（图的邻接矩阵和最短路径）
图（Graph）是由顶点（Vertex）的有穷非空集合和顶点之间边（Edge）的集合组成，通常表示为：G（V，E），其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。图中的数据元素，我们称之为顶点（Vertex），顶点集合有穷非空。在图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。
图的邻接矩阵（Adjacency Matrix)存储方式是用两个数组来表示图。
用一个顺序表来存储顶点信息
用邻接矩阵（二维数组）表示顶点间的相邻关系
图按照有无方向分为无向图和有向图。无向图由顶点和边组成，有向图由顶点和弧构成。弧有弧尾和弧头之分，带箭头一端为弧头。
图中顶点之间有邻接点、依附的概念。无向图顶点的边数叫做度。有向图顶点分为入度和出度。
图上的边或弧带有权则称为网。
在一个图中，每条边或弧可以拥有一个与之相关的数值，我们将它称为权。这些权可以具有一定的含义，比如，表示一个顶点到达另一个顶点的距离、所花费的时间、线路的造价等等。这种带权的图通常被称作网。
图中顶点间存在路径，两顶点存在路径则说明是连通的，如果路径最终回到起始点则称为环，当中不重复的叫简单路径。若任意两顶点都是连通的，则图就是连通图，有向则称为强连通图。图中有子图，若子图极大连通则就是连通分量，有向的则称为强连通分量。
图的邻接矩阵的存储结构定义如下：
#define MVNum 50 //最大顶点数
typedef struct{
VertexType vexs[MVNum];
Adjmatrix arcs[MVNum[MVNum];
}MGraph
下图是一个4个顶点的无向图：
无权无向图的邻接矩阵可定义为：
下图是一个4个顶点的有向图：
在图的术语中，我们提到了网的概念，也就是每条边上都带有权的图叫做网。那些这些权值就需要保存下来。
设图G是网图，有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：
下图是一个有向网图。
最短路径代码：
#include <stdio.h>
#include <stdlib.h>
#define MVNum 100 //最大顶点数
#define Maxint 32767
typedef char VertexType;
typedef int Adjmatrix;
typedef enum {FALSE,TRUE} boolean; //定义布尔型
typedef struct {
VertexType vexs[MVNum]; //顶点数组，类型假定为char型
Adjmatrix arcs[MVNum][MVNum]; //邻接矩阵，假定为int型
}MGraph;
//全局数组
int D1[MVNum],P1[MVNum];
int D[MVNum][MVNum],P[MVNum][MVNum];
//声明函数原型
void CreateMGraph(MGraph *,int ,int );
void Dijkstra(MGraph,int,int );
void Floyd(MGraph ,int);
void displayNode(MGraph *,int);
//主程序
void main( )
{ MGraph G;
int n,e,v,w,k;
int xz=1;
printf("输入图中顶点个数和边数n,e：");
scanf("%d %d",&n,&e);
CreateMGraph(&G,n,e);//建立图的存储结构
displayNode(&G,n);
while (xz!=0) {
printf("******求城市之间的最短路径******\n");
printf("================================\n");
printf("1.求一个城市到所有城市的最短路径\n");
printf("2.求任意的两个城市之间的最短路径\n");
printf("================================\n");
printf(" 请选择：1 或 2，选择 0 退出 ：");
scanf("%d",&xz);
if(xz==2) {
Floyd(G,n); //调用费洛伊德算法
printf(" 输入源点(或称起点)和终点：v,w ：");
scanf("%d %d",&v,&w);
k=P[v][w]; //k为起点v的后继顶点
if(k==0)
printf("顶点 %d 到 %d 无路径！\n",v,w);
else
{
printf("从顶点%d到%d的最短路径是：%d",v,w,v);
while(k!=w) {
printf("→%d",k); //输出后继顶点
k=P[k][w]; //继续找下一个后继顶点
}
printf("→%d\n",w); //输出终点w
printf(" 路径长度：%d\n",D[v][w]);
}
}
else
if(xz==1) {
printf("求单源路径，输入源点 v ：");
scanf("%d",&v);
Dijkstra(G,v,n); //调用迪杰斯特拉算法
}
// xz=0;
}
printf("结束求最短路径，再见！\n");
system("pause");
}
void CreateMGraph(MGraph* G,int n,int e)
{//采用邻接矩阵表示法构造有向网G, n、e表示图的当前顶点数和边数
int i,j,k,w;
for(i=1;i<=n;i )//输入顶点信息
G->vexs[i]=(char)i;
for(i=1;i<=n;i )
for(j=1;j<=n;j )
G->arcs[i][j]=Maxint;//初始化邻接矩阵
printf("输入%d条边的i、j及w：\n",e);
for(k=1;k<=e;k ){ //读入e条边，建立邻接矩阵
scanf("%d %d %d",&i,&j,&w);
G->arcs[i][j]=w;
}
printf("有向图的存储结构建立完毕！\n");
}
void displayNode(MGraph *G,int m)
{
int i,j;
printf("图的邻接矩阵为：\n");
for(i=1;i<=m;i )
{
for(j=1;j<=m;j )
printf("d",G->arcs[i][j]);
printf("\n");
}
}
//迪杰斯特拉算法
void Dijkstra(MGraph G,int v1,int n)
{ //用Dijkstra算法求有向图G的v1顶点到其他顶点v的最短路径P[v]及其权D[v]
//设G是有向网的邻接矩阵，若边<i,j>不存在，则G[i][j]=Maxint
//S[v]为真当且仅当v∈S,即已求得从v1到v的最短路径
int D2[MVNum],P2[MVNum];
int v,i,w,min;
boolean S[MVNum];
for(v=1;v<=n;v ){//初始化S和D
S[v]=FALSE; //置空最短路径终点集
D2[v]=G.arcs[v1][v]; //置初始的最短路径值
if(D2[v]<Maxint)
P2[v]=v1; //v1是v的前趋(双亲)
else
P2[v]=0; //v无前趋
}//end_for
D2[v1]=0;S[v1]=TRUE; //S集初始时只有源点，源点到源点的距离为0
//开始循环，每次求得v1到某个v顶点的最短路径，并加v到S集中
for(i=2;i<n;i )
{//其余n-1个顶点
min=Maxint;
for(w=1;w<=n;w )
if(!S[w] && D2[w]<min)
{
v=w;
min=D2[w];
}//w顶点离v1顶点更近
S[v]=TRUE;
for(w=1;w<=n;w )//更新当前最短路径及距离
if(!S[w]&&(D2[v] G.arcs[v][w]<D2[w]))
{ //修改D2[w]和P2[w],w∈V-S
D2[w]=D2[v] G.arcs[v][w];
P2[w]=v;
}//End_if
}//End_for
printf("路径长度 路径\n");
for(i=1;i<=n;i )
{
printf("]",D2[i]);
printf("]",i);v=P2[i];
while(v!=0) {
printf("<-%d",v);
v=P2[v];
}
printf("\n");
}
}
//费洛伊德算法
void Floyd(MGraph G,int n)
{
int i,j,k;
for(i=1;i<=n;i ) //设置路径长度D和路径path初值
for(j=1;j<=n;j )
{
if(G.arcs[i][j]!=Maxint)
P[i][j]=j; //j是i的后继
else
P[i][j]=0;
D[i][j]=G.arcs[i][j];
}
for(k=1;k<=n;k )
{//做k次迭代,每次均试图将顶点k扩充到当前求得的从i到j的最短路径Pij上
for(i=1;i<=n;i )
for(j=1;j<=n;j )
{
if(D[i][k] D[k][j]<D[i][j])
{
D[i][j]= D[i][k] D[k][j]; //修改长度
P[i][j]=P[i][k];
}
}
}
}
有如下有向图，为了操作方便，对于图的顶点都用序号来表示，顶点的字母用对应的序号来操作：a(1)，b(2)，c(3)，d(4)，e(5)，f(6)，g(7)。
运行效果如下：
输入图中顶点个数和边数n,e(空格分隔)：7 10
输入10条边的i、j(矩阵行列或坐标值)及w（权值，如距离、花费时间等）：
1 7 9
2 1 20
2 3 10
2 4 20
3 5 5
5 4 12
5 7 15
6 5 18
6 7 10
7 3 18
有向图的存储结构建立完毕！
图的邻接矩阵为：
32767 32767 32767 32767 32767 32767 9
20 32767 10 20 32767 32767 32767
32767 32767 32767 32767 5 32767 32767
32767 32767 32767 32767 32767 32767 32767
32767 32767 32767 12 32767 32767 15
32767 32767 32767 32767 18 32767 10
32767 32767 18 32767 32767 32767 32767
******求城市之间的最短路径******
================================
1.求一个城市到所有城市的最短路径
2.求任意的两个城市之间的最短路径
================================
请选择：1 或 2，选择 0 退出 ：1
求单源路径，输入源点 v ：1
路径长度 路径
0 1
32767 2
27 3<-7<-1
44 4<-5<-3<-7<-1
32 5<-3<-7<-1
32767 6
9 7<-1
******求城市之间的最短路径******
================================
1.求一个城市到所有城市的最短路径
2.求任意的两个城市之间的最短路径
================================
请选择：1 或 2，选择 0 退出 ：2
输入源点(或称起点)和终点：v,w ：1 4
从顶点1到4的最短路径是：1→7→3→5→4
路径长度：44
******求城市之间的最短路径******
================================
1.求一个城市到所有城市的最短路径
2.求任意的两个城市之间的最短路径
================================
请选择：1 或 2，选择 0 退出 ：2
输入源点(或称起点)和终点：v,w ：4 7
顶点 4 到 7 无路径！
******求城市之间的最短路径******
================================
1.求一个城市到所有城市的最短路径
2.求任意的两个城市之间的最短路径
================================
请选择：1 或 2，选择 0 退出 ：0
结束求最短路径，再见！
有如下有向网图：
运行结果：
输入图中顶点个数和边数n,e(空格分隔)：7 20
输入20条边的i、j(矩阵行列或坐标值)及w（权值，如距离、花费时间等）：
1 2 2553
2 1 2553
1 3 695
3 1 695
1 4 704
4 1 704
2 3 511
3 2 511
2 5 812
5 2 812
3 4 349
4 3 349
3 6 1579
6 3 1579
4 7 651
7 4 651
5 6 2368
6 5 2368
6 7 1385
7 6 1385
有向图的存储结构建立完毕！
******求城市之间的最短路径******
================================
1.求一个城市到所有城市的最短路径
2.求任意的两个城市之间的最短路径
================================
请选择：1 或 2，选择 0 退出 ：1
求单源路径，输入源点 v ：1
路径长度 路径
0 1
1206 2<-3<-1
695 3<-1
704 4<-1
2018 5<-2<-3<-1
2274 6<-3<-1
1355 7<-4<-1
******求城市之间的最短路径******
================================
1.求一个城市到所有城市的最短路径
2.求任意的两个城市之间的最短路径
================================
请选择：1 或 2，选择 0 退出 ：2
输入源点(或称起点)和终点：v,w ：5 7
从顶点5到7的最短路径是：5→2→3→4→7
路径长度：2323
******求城市之间的最短路径******
================================
1.求一个城市到所有城市的最短路径
2.求任意的两个城市之间的最短路径
================================
请选择：1 或 2，选择 0 退出 ：2
输入源点(或称起点)和终点：v,w ：7 2
从顶点7到2的最短路径是：7→4→3→2
路径长度：1511
******求城市之间的最短路径******
================================
1.求一个城市到所有城市的最短路径
2.求任意的两个城市之间的最短路径
================================
请选择：1 或 2，选择 0 退出 ：0
结束求最短路径，再见！
请按任意键继续. . .
－End－
,
免责声明：本文仅代表文章作者的个人观点，与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺，请读者仅作参考，并自行核实相关内容。文章投诉邮箱：anhduc.ph@yahoo.com
