图的定义和术语
图的定义
图G由两个集合构成，记作G=<V,E> ，其中V是顶点的非空有限集合，E是边的有限集合，其中边是顶点的无序对或有序对集合。
图的术语
无向图：若图G中所有边是无向边，则G为无向图
有向图：若所有边是有向边，则G为有向图；有向边被称作弧。
无向完全图：无向图且边数为n(n-1)/2
有向完全图：有向图且边数为n(n-1)
邻接点：边的两个顶点
关联边：若边e=(v,u)，则称顶点v，u关联边e
顶点的度：一个顶点的度是与它关联的边的条数
入度：以该顶点为终点的有向边的条数，ID(v)
出度：以该顶点为起点的有向边的条数，OD(v)
顶点数、边数e、和度数D(v)的关系：e=$\sum_{i=1}^nD(V_i)$/2
无向图的路径、回路：
无向图G=(V,E)中的顶点序列$v_1$,$v_2$,…,$v_k$,若($v_i$,$v_{i+1}$) $\in$ E(i=1,2,…,k-1),$v=v_1$,$u=v_k$,则称该序列是从v到u的路径；若v=u，则该序列称为回路。
有向图的路径、回路：
有向图G=(V,E)中的顶点序列$v_1$,$v_2$,…,$v_k$,若<$v_i$,$v_{i+1}$> $\in$ E(i=1,2,…,k-1),$v=v_1$,$u=v_k$,则称该序列是从v到u的路径；若v=u，则该序列称为回路。
简单路径：序列顶点中不重复出现的路径
简单回路/环：在一条路径中，除起点和终点外所有顶点各不相同
连通图：在无向图G=中，若对于任何两个顶点v,u都存在v到u的路径，则称G是连通图。
强连通图：在有向图G=中，若对于任何两个顶点v,u都存在v到u的路径，则称G是连通图。
子图：设有两个图G=(V,E)、$G_1=(V_1,E_1)$，若$V_1$ $\subseteq$V，$E_1$ $\subseteq$E，$E_1$关联的顶点都在$V_1$中，称$G_1$是G的子图。
连通分量：无向图中的极大连通子图
强连通分量：有向图中的极大强连通子图
网络(边带权图)：某些图的边具有与它相关的数，称为权，这种带权图叫网络
生成树：连通图的一个子图如果是一棵包含G所有顶点的树，则称为图G的生成树
图的抽象数据类型定义
ADT Graph{
数据对象V:V是具有相同特性的元素的集合称为顶点集。
数据关系: R={VR}
VR={<v,w>|v,w属于V且P(v,w),<v,w>表示从v到w的弧}
基本操作:
CreateGraph(&G)
DestoryGraph(&G)
InsertVex(&G,v)
DeleteVex(&G,v)
DFSTraverse(G,v,visit())
BFSTraverse(G,v,visit())
}
|
图的存储结构
数组表示法(邻接矩阵)
G的邻接矩阵满足以下条件：
邻接矩阵中的元素A[i] [j]存放的是顶点i到顶点j的关系的信息。
对于无向图
无向图的邻接矩阵特点：1.对称矩阵 2.对角线元素全0
无向图的第i个顶点的度怎么表示？ 第i行(或第i列)的非零元素个数之和
图的总度数：矩阵中非零元素个数之和
边数为总度数的一半。
对于有向图
第i个顶点的出度和入度如何体现？
第i行的非零元个数之和为出度
第i列的非零元个数之和为入度
边数为非零元的个数
网络的邻接矩阵
对于无穷大，可以用INT_MAX表示(用一个特殊的数表示即可)
存储结构：
#include <iostream>
#include<string>
#define MAX_VERTEX_NUM 100
#define IFINITY INT_MAX
#define TRUE 1
#define FALSE 0
using namespace std;
typedef enum {DG,DN,UDG,UDN}GraphKind;
typedef struct VertexType{
char id;
}VRType;
typedef struct InfoType {
int weight;
} InfoType;
typedef struct ArcCell{
int adj;
InfoType *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct {
VertexType vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;
GraphKind kind;
}MGraph;
|
创建图：
void Creategraph(MGraph &G){
int i,j,k;float w;
cout<<"请输入顶点数，弧数，图类型:";
scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&G.kind);
for(i=0;i<G.vexnum;++i){
cout<<"输入顶点名称:";
cin>>G.vexs[i].id;
}
for(i=0;i<G.vexnum;++i){
for(j=0;j<G.vexnum;j++){
G.arcs[i][j].adj=IFINITY;
G.arcs[i][j].info=NULL;
}
}
for(k=0;k<G.arcnum;k++){
cout<<"输入邻接矩阵位置与权重:";
scanf("%d,%d,%f",&i,&j,&w);
G.arcs[i][j].adj=w;
G.arcs[j][i].adj=w;
}
}
|
特点
1.空间复杂度O($n^2$)
2.边或弧的插入和删除操作简单，但顶点的插入和删除操作不容易
邻接表
对于每个顶点，建立一个单链表，存储该顶点的所有邻接顶点和信息·。
对于无向图
第i个顶点的总度数为边链表的结点的个数
图的总度数为所有边链表的结点个数之和。
边数即所有边链表的结点个数之和的一半
邻接表的定义
邻接表分为两部分，边链表和顶点表
存储结构：
#include <iostream>
#include<string>
#define MAX_VERTEX_NUM 20
using namespace std;
typedef enum {DG,DN,UDG,UDN}GraphKind;
typedef struct InfoType {
int weight;
}InfoType;
typedef struct vertextype{
char id;
}vertextype;
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
InfoType *info;
}ArcNode;
typedef struct vnode{
vertextype data;
ArcNode *firstarc;
}vnode,adjlist[MAX_VERTEX_NUM];
typedef struct {
adjlist vertices;
int vexnum,arcnum;
GraphKind kind;
}ALGraph;
|
创建图：
void Creatadilist(ALGraph &G){
int i,j,k;
ArcNode *s;
scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&G.kind);
for(i=0;i<G.vexnum;i++){
cin>>G.vertices[i].data.id;
G.vertices[i].firstarc=NULL;
}
for(k=0;k<G.arcnum;k++){
cin>>i>>j;
s=(ArcNode*)malloc(sizeof(ArcNode));
s->adjvex=j;
s->info=NULL;
s->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=s;
}
}
|
特点
1.空间复杂度O(n+e)
2.容易找到任意一个顶点的第一个邻接点
图的遍历
图的遍历指，从图的某一顶点出发，访问图中所有顶点，且每个顶点仅访问一次
深度优先搜索
基本思想
1.首先访问图中某一个顶点$V_1$，以该点为出发点
2.任选一个与顶点$V_i$邻接的未被访问的顶点$V_j$，访问$V_j$
3.以$V_j$为新的出发点继续进行深度优先搜索
算法概要
输入：图G，初始访问顶点v;
输出：图G的深度优先搜索序列；
1.访问v
2.改变v的访问标志
3.任选一个与v相邻又没被访问的顶点w
4.从w开始继续进行深度优先搜索
算法实现：
这里用邻接矩阵实现算法，传入的visit[]数组全部置0
void DFS(MGraph G, int v, bool visited[]) {
visited[v] = TRUE;
cout << G.vexs[v].id;
for (int w = 0; w < G.vexnum; w++) {
if (G.arcs[v][w].adj != -1 && !visited[w]) {
DFS(G, w, visited);
}
}
}
|
广度优先搜索
基本思想
1.首先访问图中某一个指定的出发点$v_i$,
2.然后一次访问$v_i$的所有邻接点$v_{i1}$,$v_{i2}$,$v_{i3}$…
3.再依次以$v_{i1}$,$v_{i2}$,$v_{i3}$…为顶点访问各顶点未被访问的邻接点，依次类推，直到图中所有顶点均被访问
算法概要
输入：图G，初始访问结点v
输出：图G的广度优先搜索序列
1.设置辅助队列Q，访问节点v，修改v的标志，v入队列
2.while(队列非空){
出队列节点u
访问与u的所有节点
修改与u邻接的所有结点的标志，与u邻接的所有结点入队列
}
typedef struct QNode{
int data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
void InitQueue(LinkQueue &Q)
{
Q.front=Q.rear=(QNode*)malloc(sizeof(QNode));
if(!Q.front)
exit(0);
Q.front->next=NULL;
}
void EnQueue(LinkQueue &Q,int e)
{
QueuePtr p=(QNode*)malloc(sizeof(QNode));
if(!p)
exit(0);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
}
void DeQueue(LinkQueue &Q,int &e)
{
if(Q.rear==Q.front)
return;
else
{
QueuePtr p;
p=Q.front->next;
e=p->data;
Q.front->next=Q.front->next->next;
if(Q.rear==p)
Q.rear=Q.front;
free(p);
}
}
int QueueEmpty(LinkQueue Q){
if(Q.front==Q.rear) return 1;
else return 0;
}
LinkQueue Q;
void BFSTraVErse(ALGraph G,bool visit[]){
int v;
for(v=0;v<G.vexnum;++v){
visit[v]=FALSE;
}
InitQueue(Q);
for(v=0;v<G.vexnum;++v){
if(!visit[v]){
visit[v]=TRUE;
cout<<G.vertices[v].data.id;
EnQueue(Q, v);
while(!QueueEmpty(Q)){
int u,w;
ArcNode *p;
DeQueue(Q, u);
for(p=G.vertices[u].firstarc;p!=NULL;p=p->nextarc)
{
if(!visit[p->adjvex])
{
w=p->adjvex;
visit[w]=TRUE;
EnQueue(Q,w);
cout<<G.vertices[w].data.id;
}
}
}
}
}
}
|
图的连通性问题
最小生成树
prim算法
#include <iostream>
#define MAX_VERTEX_NUM 100
using namespace std;
typedef struct ArcCell{
float adj;
}ArcCell,G[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
struct Edge{
char begin;
char end;
float weight;
};
typedef struct{
G arcs;
int vexnum,arcsnum;
char vex[MAX_VERTEX_NUM];
Edge edge[MAX_VERTEX_NUM];
}MGraph;
struct V{
int adjvex;
float lowcost;
};
V closedge[MAX_VERTEX_NUM];
int Locatevex(MGraph G,char u){
int i;
for(i=0;i<G.vexnum;i++){
if(G.vex[i]==u){
return i;
}
}
return -1;
}
void CreateGraph(MGraph &G){
int i,j,k;
char name;
float w;
char ii, jj;
scanf("%d %d",&G.vexnum,&G.arcsnum);
for(i=0;i<G.vexnum;i++){
getchar();
scanf("%c",&name);
G.vex[i]=name;
}
for(i=0;i<G.vexnum;i++){
for(j=0;j<G.vexnum;j++){
G.arcs[i][j].adj=100;
}
}
for(i=0;i<G.arcsnum;i++){
getchar();
scanf("%c %c %f",&ii,&jj,&w);
j=Locatevex(G, ii);
k=Locatevex(G, jj);
G.arcs[j][k].adj=w;
G.arcs[k][j].adj=w;
}
}
void showMatrix(MGraph G){
int i,j;
for(i=0;i<G.vexnum;i++){
for(j=0;j<G.vexnum;j++){
cout<<G.arcs[i][j].adj<<" ";
}
cout<<endl;
}
}
void MiniSpanTree_P(MGraph G,char u){
V closedge[G.vexnum];
int t=Locatevex(G,u);
int i,j,k=0;
for(j=0;j<G.vexnum;j++){
if(j!=t){
closedge[j]={t,G.arcs[t][j].adj};
}
closedge[t].lowcost=0;
}
for(i=0;i<G.vexnum;i++){
float temp=100;
for(j=0;j<G.vexnum;j++){
if(closedge[j].lowcost==0){
continue;
}
else{
if(closedge[j].lowcost<temp){
k=j;
temp=closedge[j].lowcost;
}
}
}
printf("%c",G.vex[closedge[k].adjvex]);
if(i==G.vexnum-1){
cout<<endl;
break;
}
else{
printf("->");
}
closedge[k].lowcost=0;
t=k;
for(j=0;j<G.vexnum;j++){
if(!closedge[j].lowcost){
closedge[j].adjvex=t;
}
else{
closedge[j].adjvex=t;
closedge[j].lowcost=G.arcs[t][j].adj;
}
}
}
}
int main(){
MGraph G;
CreateGraph(G);
showMatrix(G);
cout<<"==============="<<endl;
char index;
cin>>index;
MiniSpanTree_P(G, index);
}
|
kruskal算法
#include <iostream>
#include <algorithm>
using namespace std;
struct Edge {
int src, dest;
float weight;
};
int findParent(int parent[], int i) {
if (parent[i] == -1)
return i;
return findParent(parent, parent[i]);
}
void unionSets(int parent[], int x, int y) {
int xset = findParent(parent, x);
int yset = findParent(parent, y);
parent[xset] = yset;
}
void kruskalMST(int V, Edge edges[], int E) {
Edge result[V - 1];
int i = 0;
int e = 0;
sort(edges, edges + E, [](Edge a, Edge b) {
return a.weight < b.weight;
});
int parent[V];
fill(parent, parent + V, -1);
while (i < V - 1 && e < E) {
Edge nextEdge = edges[e++];
int x = findParent(parent, nextEdge.src);
int y = findParent(parent, nextEdge.dest);
if (x != y) {
result[i++] = nextEdge;
unionSets(parent, x, y);
}
}
cout << "Edges in the Minimum Spanning Tree:" << endl;
for (i = 0; i < V - 1; ++i) {
cout << result[i].src << " - " << result[i].dest << " : " << result[i].weight << endl;
}
}
int main() {
int V = 4;
int E = 5;
Edge edges[] = {
{0, 1, 10},
{0, 2, 6},
{0, 3, 5},
{1, 3, 15},
{2, 3, 4}
};
kruskalMST(V, edges, E);
return 0;
}
|
有向无环图的应用
有向无环图简称DAG图
DAG图在工程计划和管理方面应用广泛。
拓扑排序
基本定义和特点
顶点活动网：AOV网，将顶点表示活动，边表示活动之间的关系
拓扑序列：把AOV网中的所有顶点排成可以线性序列，该序列满足：若AOV网中存在从$v_i$到$v_j$的路径，则在该序列中，$v_i$必位于$v_j$之前
拓扑排序：构造AOV网的拓扑序列的操作被称为拓扑排序
特点：
1.一个有向图的拓扑序列不一定唯一
2.有向无环图一定存在拓扑序列
3.有向有环图不存在拓扑序列
4.可以通过构造拓扑序列，判断AOV网是否存在环
拓扑排序算法的基本思想
1.在有向图中选一个入度为0的顶点输出
2。从图中删除该顶点及所有它的出边
3.重复 1和2 直到所有顶点输出或者图中剩余顶点入度均不为0（此时图中有回路，无法拓扑排序）
算法概要
增加一个存放各顶点入度的数组indegree[]
1.扫描indegree[]，将入度为0的顶点入栈
2.while(栈非空){
出栈顶元素$v_i$，并输出；
检查$v_i$的出边表，将每条出边<$v_i$,$v_j$>的终点$v_j$的入度减1，若vj的入度减至0，v$v_j$入栈；
}
3.若输出的顶点数小于n则有回路（无法拓扑排序），否则正常结束。
算法实现：
#include <iostream>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define MAX_VERTEX_NUM 20
#define FALSE 0
#define TRUE 1
#define ERROR 0
#define OK 1
using namespace std;
typedef enum {DG,DN,UDG,UDN}GraphKind;
typedef struct InfoType {
int weight;
}InfoType;
typedef struct vertextype{
char id;
int No;
}vertextype;
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
InfoType *info;
}ArcNode;
typedef struct vnode{
vertextype data;
ArcNode *firstarc;
}vnode,adjlist[MAX_VERTEX_NUM];
typedef struct {
adjlist vertices;
int vexnum,arcnum;
GraphKind kind;
}ALGraph;
void Creatadilist(ALGraph &G){
int i,j,k;
ArcNode *s;
scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&G.kind);
for(i=0;i<G.vexnum;i++){
cin>>G.vertices[i].data.id;
G.vertices[i].firstarc=NULL;
}
for(k=0;k<G.arcnum;k++){
cin>>i>>j;
s=(ArcNode*)malloc(sizeof(ArcNode));
s->adjvex=j;
s->info=NULL;
s->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=s;
}
}
struct SElemType{
int a;
int b;
};
typedef struct{
int *base;
int *top;
int stacksize;
}SqStack;
void InitStack(SqStack &S){
S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));
if(!S.base) exit(0);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
}
void Push(SqStack &S,int e){
if(S.top-S.base>=S.stacksize){
S.base=(int*)realloc(S.base, (S.stacksize+STACKINCREMENT)*sizeof(int));
if(!S.base) {
exit(0);
}
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
}
void Pop(SqStack &S,int &e){
if(S.top==S.base){
exit(0);
}
else{
e=*(S.top-1);
S.top--;
}
}
void Clear(SqStack &S){
while(S.top>S.base){
int* p=S.top;
S.top--;
free(p);
S.stacksize-=STACKINCREMENT;
}
}
void DestroyStack(SqStack &S){
if (S.base != NULL ){
Clear(S);
free(S.base);
S.base = NULL;
S.top = NULL;
S.stacksize = 0;
}
}
int StackEmpty(SqStack S){
if(S.base==S.top) return 1;
else return 0;
}
int StackLength(SqStack S){
if(!(S.base==S.top)) return S.top-S.base;
else return 0;
}
void GetTop(SqStack S,int &e){
e=*(S.top-1);
cout<<"e is:"<<(&e)<<"-"<<(&e)<<endl;
}
void StackTravers(SqStack S){
int i=1;
if(StackEmpty(S))
{
cout<<"Stack is Empty."<<endl;
exit(0);
}
while(!(S.top==S.base)){
S.top--;
cout<<i<<". ";
cout<<(*(&S.top))<<endl;
i++;
}
}
void FindInDegree(ALGraph G, int indegree[]){
int i;ArcNode *p;
for(i=0;i<G.vexnum;i++){
p=G.vertices[i].firstarc;
while(p){
indegree[p->adjvex]++;
p=p->nextarc;
}
}
}
int TopologicalSort(ALGraph G){
SqStack S;
int count,k,i;
ArcNode *p;
int indegree[MAX_VERTEX_NUM]={0};
FindInDegree(G, indegree);
InitStack(S);
for(i=0;i<G.vexnum;++i){
if(!indegree[i]) Push(S, i);
}
count=0;
while(!StackEmpty(S)){
Pop(S,i);
printf("%d %d",i,G.vertices[i].data.No);
++count;
for(p=G.vertices[i].firstarc;p;p=p->nextarc){
k=p->adjvex;
if(!(--indegree[k])) Push(S, k);
}
}
if(count<G.vexnum)return ERROR;
else return OK;
}
|
最短路径
问题提出
路径长度：路径上边的权值之和
最短路径：两结点间权值之和最小的路径
单源最短路径Dijkstra
给定有向图G和源点$v_i$，求$v_i$到G中其余各顶点的最短路径
算法思想
按路径长度的递增次序，逐步产生最短路径Dijkstra算法(SPF算法)
首先求出长度最短的一条路径，再参照它求出长度次短的一条最短路径，以此类推，直到从顶点v到其他各顶点的最短路径全部求出为止
算法要点
例图：
1.设源点$v_0$，顶点集合分成两部分：
U：已经求出最短路径的顶点集合
V-U：未求出最短路径的顶点集合
初值：U={$v_0$},V-U={$v_1$,$v_2$,$v_3$,$v_4$}
第二个加入U中的顶点必然是与$v_0$邻接且与$v_0$之间的边长最短的顶点
2.U={$v_0$,$v_2$}，V-U={$v_1$,$v_3$,$v_4$}
设第三个加入U中的顶点是w$\in$V-U,则w到$v_0$的最短路径的特点是：w是V-U中满足$v_0$->w和$v_0$->$v_2$->w中最短的
存储结构
#include <iostream>
#define MAX_VERTEX_NUM 100
typedef struct {
int vexs[MAX_VERTEX_NUM];
float arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int vexnum,arcnum;
}MGraph;
|
算法概要
1.引入辅助数组D[ ],D[i]表示当前所找到的源点到每个终点i的最短路径长度，最短路径的初值即有向边的权值D[i]=G.arcs[$v_0$] [i]
引入辅助数组final[ ],final[i]=1表示顶点i的最短路径已经求出，否则未求出
初始状态：final[$v_0$]标志为1，其余为0
引入数组P[ ]来记录路径
2.选择D[ ]中路径最小值的顶点v(已经求出最短路的顶点除外)
v就是当前求得得一条从$v_0$出发的最短路径的终点，修改final[v]=1
3.修改未求出最短路径的顶点的最短路径长度，如果D[v]+G.arcs[v] [w]<D[w]
则修改D[w]，D[w]=D[v]+G.arcs[v] [w]
同时修改P[w]=v
4.重复2 ，3操作 n-1次，求得最短路径长度递增序列
算法实现
#include <iostream>
using namespace std;
#define MAX_VERTEX_NUM 100
#define INFINITY 1000
typedef struct ArcCell {
int adj;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM];
typedef struct {
int vexs[MAX_VERTEX_NUM];
float arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int vexnum,arcnum;
}MGraph;
void ShortestPath_DIJ(MGraph G,int v0,int *P,float *D){
int i=0,v,w,min,f[MAX_VERTEX_NUM];
for(v=0;v<G.vexnum;++v){
f[v]=0;
D[v]=G.arcs[v0][v];
P[v]=-1;
if(D[v]<INFINITY) P[v]=0;
}
f[0]=1;P[0]=-1;
for(int j=0;j<5;j++){
cout<<D[j]<<" ";
}
cout<<endl;
for(int j=0;j<5;j++){
cout<<f[j]<<" ";
}
cout<<endl;
for(int j=0;j<5;j++){
cout<<P[j]<<" ";
}
cout<<endl;
for(i=1;i<G.vexnum;++i){
min=INFINITY;
for(w=0;w<G.vexnum;++w){
if(!f[w])
if(D[w]<min){v=w;min=D[w];}
}
f[v]=1;
for(w=0;w<G.vexnum;++w){
if((!f[w])&&(min+G.arcs[v][w]<D[w])){
D[w]=min+G.arcs[v][w];
P[w]=v;
}
}
}
int pre;
for(i=1;i<G.vexnum;i++){
printf("\n%.0f:%d",D[i],i);
pre=P[i];
while(pre!=-1){
printf("<-%d",pre);
pre=P[pre];
}
}
}
int main(int argc, const char * argv[]) {
MGraph G;
G.vexnum=5;
for(int i=0;i<5;++i){
for(int j=0;j<5;j++){
G.arcs[i][j]=INFINITY;
}
}
G.arcs[0][0]=0;
G.arcs[1][1]=0;
G.arcs[2][2]=0;
G.arcs[3][3]=0;
G.arcs[4][4]=0;
G.arcs[0][1]=6;
G.arcs[0][2]=3;
G.arcs[1][3]=5;
G.arcs[2][1]=2;
G.arcs[2][3]=3;
G.arcs[2][4]=4;
G.arcs[3][4]=2;
float *D = new float[G.vexnum];
int *P = new int[G.vexnum];
ShortestPath_DIJ(G, 0, P,D);
delete[] D;
delete[] P;
}
|
算法分析
Dijkstra算法的时间复杂行主要体现在求每个顶点的最短路径是，需要修改距离和求最小值，时间复杂性O($n^2$)
Dijkstra算法的空间复杂性主要体现在辅助数组，空间复杂性为O(n)
每一对顶点之间的最短路径
依次把有向网络的每个顶点作为源点，重复执行Dijkstra算法n次，即可求得每对顶点之间的最短路径
Floyd算法 可以直接求出所有顶点之间的最短路径
算法思想
对顶点进行编号，设顶点为0,1,…,n-1，算法采用邻接矩阵G.arcs[n] [n]表示有向网络
$D^{(-1)}[n][n]$表示中间不经过任何点的最短路径；即邻接矩阵
$D^{(0)}[n][n]$表示只允许经过0号顶点的最短路径
$D^{(1)}[n][n]$表示只允许经过0号和1号顶点的最短路径
$…….$
$D^{(n-1)}[n][n]$表示可经过所有顶点的最短路径
基本想法：动态规划算法
如果$v_i$与$v_j$之间有一条路径，但不一定最短，也许经过某些中间点会使路径长度更短，尝试在原路径中加入其他顶点作为中间顶点
