算法设计与分析作业二之Floyd算法和Dijkstra算法的图解和代码实现

Floyd算法：
一、问题描述：
从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，算法假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，算法检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。

用Floyd算法求解下图各个顶点的最短距离。写出Floyd算法的伪代码和给出距离矩阵（顶点之间的最短距离矩阵）；

二、算法核心步骤（伪代码）及图解：

1. 将图转化为邻接矩阵（主对角线，也就是自身到自身，我们规定距离为0，不可达为无穷大）；
2. 再创建一个二维数组P路径数组，用于存放任意一对顶点之间的最短路径。（初始还未开始查找，默认-1）
3. 列举所有的路径，转化成二元数组；
4. 依次选择编号为1,2,3,4的点为中间点，(以1为例)；判断 (D[ i ][ 1 ]+D[ 1 ][ j ] ) < D[ i ][ j ] 如果表达式为真，更新D[ i ] [ j ]的值为D[ i ] [ 1 ] + D[ 1 ] [ j ]，P[ i ] [ j ]的值为点1（即设置i到j要经过1点中转）；
5. 根据最终结果，就可以知道任意2点的最短距离和路径

图解：

三、代码实现：

#include <stdio.h>        
#define INFINITY 65535 

typedef int VertexType;
typedef int EdgeType; 

typedef struct //图的邻接矩阵存储结构
{
    VertexType vexs[4]; //顶点向量  
    EdgeType edges[4][4];  //邻接矩阵 
    int vexnum,arcnum; //顶点数和边数 
}MGraph; 
 
void CreateGraph(MGraph *G) 
{
    int i,j,k,weight;
    int a,b;
    printf("请输入顶点数和边数:");
    scanf("%d,%d",&(G->vexnum),&(G->arcnum));
	printf("请输入顶点名称：");
	for(i=0;i<G->vexnum;i++)
	{
	   getchar();
	   scanf("%d",&(G->vexs[i]));
	}  
	for(i=0;i<G->vexnum;i++) 
	   for(j=0;j<G->vexnum;j++) 
	      if(i==j)
		  {
		  	G->edges[i][j]=0; 
		  } 
		  else
		  G->edges[i][j]=INFINITY;
		  for(k=0;k<G->arcnum;k++) 
		  { 
		  printf("请输入第%d条边的两个顶点名称：",k+1); 
		  scanf("%d,%d",&a,&b); 
		  for(i=0;a!=G->vexs[i];i++); 
		  for(j=0;b!=G->vexs[j];j++); 
		  getchar(); 
		  printf("请输入第%d条边的权值：",k+1); 
		  scanf("%d",&weight);  
		  G->edges[i][j]=weight;
		  }
} 
  
void Floyd(MGraph G,int P[4][4],int D[4][4]) 
{
    int v,w,k; 
    for(v=0;v<G.vexnum;v++)//初始化D和P 
    { 
      for(w=0;w<G.vexnum;w++) 
      {
	     D[v][w]=G.edges[v][w];
		 P[v][w]=w;
	  }
	} 
	for(k=0;k<G.vexnum;k++) 
	{
	   for(v=0;v<G.vexnum;v++)
	   {
	      for(w=0;w<G.vexnum;w++)
		  {
		  if(D[v][w]>(D[v][k]+D[k][w]))
		  {
		     D[v][w]=D[v][k]+D[k][w];
		     P[v][w]=P[v][k]; 
		  }
		  }
	   }
	}
}
 
int main() 
{
    MGraph G; 
    CreateGraph(&G); 
    int i,j; 
    printf("edgesnum:%d\n",G.arcnum); 
    printf("vexesnum:%d\n",G.vexnum); 
    for(i=0;i<4;i++) 
    { 
      for(j=0;j<4;j++) 
      printf("%d ",G.edges[i][j]); 
      printf("\n");
	} 
    int v,w,k; 
    int P[4][4]; 
    int D[4][4]; 
    Floyd(G,P,D); 
    for(v=0;v<G.vexnum;v++) 
    { 
      for(w=0;w<G.vexnum;w++) 
      {
	   if(v!=w)
       printf("v%d to v%d weight:%d ",v,w,D[v][w]); 
       k=P[v][w]; 
       printf("path:%d",v);
       while(k!=w) 
       { 
	    printf("->%d",k); 
        k=P[k][w]; 
       } 
       printf("->%d\n",w); 
      } 
    }
}

四、Floyd算法时间复杂度分析：
算法中的三个for循环，时间复杂度为O(N^3）；

Dijkstra算法：
一、问题描述：
首先把起点到所有点的距离存下来找个最短的，然后再找出最短的，遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近，如果更近了就更新距离，这样把所有的点找遍之后就存下了起点到其他所有点的最短距离。

对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。

二、算法核心步骤（伪代码）及图解：

1. 首先使用二维数组D来存储顶点之间边的关系；
2. 还要用一个一维数组 dis 来存储 a点到其余各个顶点的初始路程，我们可以称 dis 数组为“距离表”。将此时 dis 数组中的值称为最短路的“估计值”。
3. 求a点到h点最短路程，那就先找一个离a点最近的点。通过数组 dis 可知当前离 a 点最近是 b点。当选择了 b点后，a点到 b点的最短路程就是当前 dis[b]值。
4. 接着再看b点有哪些出边。有b->d;比较 dis[d]和 dis[b]+D[b][d]的大小,因为dis[d]>dis[b]+D[b][d],因此dis[d]更新为3.
5. 再从剩下的c,e,f,g,h点中找离a点最近的点，进行松弛，直到a点到所有顶点的最短路径都找到。
6. 最后dis数组中h对应的值就是我们要求的a点到h点的最短路径。

图解：

三、代码实现：

#include <stdio.h>
#define MAX_NUM 9                   
#define VRType int 
#define VertexType int 
#define INFINITY 65535

typedef struct 
{
    VertexType vexs[MAX_NUM];       
    VRType arcs[MAX_NUM][MAX_NUM];
    int vexnum,arcnum; 
}MGraph;

typedef int PathMatrix[MAX_NUM];    
typedef int ShortPathTable[MAX_NUM]; 

int LocateVex(MGraph * G,VertexType v)
{
    int i=0;
    //遍历一维数组，找到变量v
    for (i=0; i<G->vexnum; i++) 
	{
        if (G->vexs[i]==v) 
		{
            break;
        }
    }
    if (i>G->vexnum) 
	{
        printf("no such vertex.\n");
        return -1;
    }
    return i;
}
//构造有向网
void CreateUDG(MGraph *G)
{
	printf("请输入顶点数和边数：");
    scanf("%d,%d",&(G->vexnum),&(G->arcnum));
    printf("请输入顶点：\n");
    for (int i=0; i<G->vexnum; i++) 
	{
        scanf("%d",&(G->vexs[i]));
    }
    for (int i=0; i<G->vexnum; i++) 
	{
        for (int j=0; j<G->vexnum; j++) 
		{
            G->arcs[i][j]=INFINITY;
        }
    }
    printf("请输入顶点及其间权值：\n");
    for (int i=0; i<G->arcnum; i++) 
	{
		int  v1,v2,w;
        scanf("%d,%d,%d",&v1,&v2,&w);
        int n=LocateVex(G, v1);
        int m=LocateVex(G, v2);
        if (m==-1 ||n==-1) {
            printf("no this vertex\n");
            return;
        }
        G->arcs[n][m]=w;
    }
}

void Dijkstra(MGraph G,int v0,PathMatrix *p,ShortPathTable *D)
{
    int final[MAX_NUM];
    for (int v=0; v<G.vexnum; v++) 
	{//初始化
        final[v]=0;
        (*D)[v]=G.arcs[v0][v];
        (*p)[v]=0;
    }
    (*D)[v0]=0;
    final[v0]=1;
    int k = 0;
    for (int i=0; i<G.vexnum; i++)
	{
        int min=INFINITY;
        for (int w=0; w<G.vexnum; w++) 
		{
            if (!final[w]) 
			{
                if ((*D)[w]<min) 
				{
                    k=w;
                    min=(*D)[w];
                }
            }
        }
        final[k]=1;
        for (int w=0; w<G.vexnum; w++)
		{
            if (!final[w]&&(min+G.arcs[k][w]<(*D)[w])) 
			{
                (*D)[w]=min+G.arcs[k][w];
                (*p)[w]=k;//记录各个最短路径上存在的顶点
            }
        }
    }
}
int main(){
    MGraph G;
    CreateUDG(&G);
    PathMatrix P;
    ShortPathTable D;
    Dijkstra(G, 0, &P, &D);
    printf("a点到各顶点的最短路径长度为:\n");
    for (int i=1; i<G.vexnum; i++) 
	{
        printf("%d - %d : %d \n",G.vexs[0],G.vexs[i],D[i]);
    }
    return 0;
}

四、Dijkstra算法时间复杂度分析：
Dijkstra算法的时间复杂度为O(N^2)；