其实就是矩阵的乘法
乘积C的第m行第n列的元素等于矩阵A的第m行的元素与矩阵B的第n列对应元素乘积之和
2次幂是 1 2 3 1
0 0 0 1
0 0 1 0
0 0 0 0
先画出有向图，再计算点到点长度为2的通路条数，这就是他的2次幂。
如下，c语言写的~~
#define MAXNUM 30
#define INFINITY 10000
#define FALSE 0
#define TRUE 1
#define BACK -1
#include "stdio.h"
#include <stdio.h>
#include "malloc.h"
定义图的构造体
typedef struct{
char vexs[MAXNUM];
int edges[MAXNUM][MAXNUM];
int n,e;
}Mgraph;
图的输入方法
void CreateGraph(Mgraph *g){
int i,j,k,w;
char ch;
printf("请输入结点数与弧数，如：3,2：");
scanf("%d,%d",&(g->n),&(g->e));
初始化权值
for(i=0;i<g->n;i++){
for(j=0;j<g->n;j++){
if(i==j){
g->edges[i][j]=0;
}else{
g->edges[i][j]=INFINITY;
}
}
}
获取权值
printf("\n为方便演示，结点内容预设为结点序号，无需输入。\n\n下面请输入弧及权值，例如：若点0到1有弧可达，且权值为10，则输入:0,1,10。注意：输入时不区分弧的顺序。\n");
for(k=0;k<g->e;k++){
printf("\t请输入第%d个弧及权值：",k+1);
scanf("%d,%d,%d",&i,&j,&w);
g->edges[i][j]=w;
}
输出邻接矩阵
printf("\n邻接矩阵：\n",k);
for(i=0;i<g->n;i++){
printf("\t");
for(j=0;j<g->n;j++){
if(g->edges[i][j]>=INFINITY){
printf("∞\t");
}else{
printf("%d\t",g->edges[i][j]);
}
}
printf("\n");
}
}
void ShortPath(Mgraph *g,int v0){
/*定义多个变数与阵列，其中R阵列为记录路径的阵列，iterator为游标，
D为距离阵列，final阵列记录是否已取到最短路径
*/
int i,j,v,w,min;
int R[MAXNUM][MAXNUM];
int iterator[MAXNUM];
int D[MAXNUM];
int final[MAXNUM];
初始化游标为零
for(i=0;i<MAXNUM;i++){
iterator[i]=0;
}
初始化final为FALSE，D为弧的权值
for(v = 0;v < g->n; ++v){
final[v] = FALSE;
D[v] = g->edges[v0][v];
}
初始化v0的路径距离为零，设定已获取最短路径
D[v0] = 0;
final[v0] = TRUE;
主回圈，获取其他的最短路径
for(i = 1;i < g->n; ++i){
min = INFINITY;
寻找最小的D[w]
for(w = 0;w < g->n; ++w){
if(final[w] != TRUE){
if(D[w]<min){
v=w;
min=D[w];
}
}
}
将找到的v设定已获取最短路径
final[v]=TRUE;
列印输出该路径
if(min!=INFINITY){
printf("\t点%d到点%d的最小路径值为：%d\t",v0,v,D[v]);
printf("路径为：%d->",v0,v,v0);
for(j=0;j<iterator[v];j++){
printf("%d->",R[v][j]);
}
printf("%d\n",v);
}
更新D[w]
for(w = 0;w < g->n; ++w){
if((final[w] != TRUE) && (min+g->edges[v][w] < D[w])){
更新路径
iterator[w]=iterator[v];
for(j=0;j<iterator[v];j++){
R[w][j]=R[v][j];
}
R[w][iterator[w]]=v;iterator[w]++;
D[w] = min + g->edges[v][w];
}
}
}
若final始终为FALSE，则不可达
for(w = 0;w<g->n; ++w){
if(final[w] != TRUE){
printf("\t点%d到点%d不可达\n",v0,w);
}
}
}
主方法
void main(){
Mgraph * g;
int i=0;
g=(Mgraph *)malloc(sizeof(Mgraph));
printf("该程式实现了Dijkstra演算法，支援路径显示，请按提示输入资料：\n\n");
CreateGraph(g);
printf("\n最小路径判断(以0点为起点)：\n");
ShortPath(g,0);
getch();
}
设邻接矩阵表示的图有i个节点，那么求距离矩阵就是求从某节点出发，到另外(i-1)个节点的最短路径。
距离矩阵的对角线必定为0，并且关于对角线对称。
就是说只要做i(i-1)/2次最短路径就可以了。
为对称矩阵。根据矩阵性质可知原因：邻接矩阵（AdjacencyMatrix）：是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn}。G的邻接矩阵是一个具有下列性质的n阶方阵：对无向图而言，邻接矩阵一定是对称的，而且对角线一定为零。无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称。因此，用邻接矩阵来表示一个具有n个顶点的有向图时需要n^2个单元来储存邻接矩阵；对有n个顶点的无向图则只存入上（下）三角阵中剔除了左上右下对角线上的0元素后剩余的元素，故只需1+2++(n-1)=n(n-1)/2个单元。无向图邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度。
这是图论的知识，OD矩阵是图顶点的出度的矩阵 图的邻接矩阵如下介绍 1．图的邻接矩阵表示法 在图的邻接矩阵表示法中： ① 用邻接矩阵表示顶点间的相邻关系 ② 用一个顺序表来储存顶点资讯 2．图的邻接矩阵(Adacency Matrix) 设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵： 【例】下图中无向图G 5 和有向图G 6 的邻接矩阵分别为A l 和A 2 。 从图的邻接矩阵表示法中可以得到如下结论： （1）对于n个顶点的无向图，有A（i，i）=0，1≤i≤n。 （2）无向图的邻接矩阵是对称的，即A（i，j）=A（j，i），1≤i≤n，1≤j≤n。 （3）有向图的邻接矩阵不一定对称的。因此用邻接矩阵来表示一个具有n个顶点的有向图时需要n 2 个单位来储存邻接矩阵；对有n个顶点的无向图则需存入上（下）三角形，故只需n（n+1）/2个单位。 （4）无向图的邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度TD（v i ）。 （5）有向图的邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的出度OD（v i ）[或入度ID（v i ）]。 3．网（带权值的图）的邻接矩阵 若G是网路，则邻接矩阵可定义为： 其中： w ij 表示边上的权值； ∞表示一个计算机允许的、大于所有边上权值的数。 【例】下面(a)是一个带权图，（b）是对应的邻接矩阵的储存结构 （a）带权图 （b）邻接矩阵 4．邻接矩阵的图类 const int MaxVertices=10; const int MaxWeight=32767; class AdjMWGraph { private: int Vertices[10]; 顶点资讯的阵列 int Edge[MaxVertices][MaxVertices]; 边的权值资讯的矩阵 int numE; 当前的边数 int numV; 当前的顶点数 public: ………; 公有函式 private: ………; 私有函式 } 注意： ① 在简单应用中，可直接用二维阵列作为图的邻接矩阵（顶点表及顶点数等均可省略）。 ② 当邻接矩阵中的元素仅表示相应的边是否存在时，EdgeTyPe可定义为值为0和1的列举型别。 ③ 无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可压缩储存。 ④ 邻接矩阵表示法的空间复杂度S(n)=0(n 2 )。
可以用Floyd法.先在d(i,j)内填入邻接矩阵
列举i,j,k, d(i,j)=min{d(i,k)+d(k,j)}
最后得到的d就是距离矩阵
比如 ：map[N][N]；
大多都是存两点之间的距离，时间等边权。
邻接矩阵是图的一种储存形式，是以二维阵列表示有n个顶点的图，而矩阵中表示图中顶点之间弧资讯的储存方式。
所谓三元组就是指，用三个变数来表示一个矩阵的情况，row 表示该元素所在的行号，col 表示该元素所在的列号，e 表示该元素的值。row col e 是三元组的基本结构。。
一般用邻接矩阵来表示图，这是e所代表的值可以为0或者1，表示相邻的两个点是否有关，即是否有线相连。e也可以表示相邻两点所在直线的权值。。