数据结构学习笔记05图 (邻接矩阵 邻接表-->BFS DFS、最短路径)

数据结构之图

图(Graph)

包含
　　一组顶点：通常用V (Vertex) 表示顶点集合
　　一组边：通常用E (Edge) 表示边的集合
　　　　边是顶点对：(v, w) ∈E ，其中v, w ∈ V
　　　　有向边<v, w> 表示从v指向w的边（单行线）
　　　　不考虑重边和自回路

无向图：边是无向边(v, w)

有向图：边是有向边<v, w>

连通：如果从V到W存在一条（无向）路径，则称V和W是连通的

连通图(Connected Graph)：如果对于图的任一两个顶点v、w∈V，v和w都是连通的，则称该图为连通图。图中任意两顶点均连通。

连通分量(Connected Component):无向图中的极大连通子图。

　　极大顶点数：再加1个顶点就不连通了
　　极大边数：包含子图中所有顶点相连的所有边

强连通：有向图中顶点V和W之间存在双向路径，则称V和W是强连通的。
强连通图：有向图中任意两顶点均强连通。
强连通分量：有向图的极大强连通子图。

路径：V到W的路径是一系列顶点{V, v1, v2, …,vn, W}的集合，其中任一对相邻的顶点间都有图中的边。路径的长度是路径中的边数（如果带权，则是所有边的权重和）。

　　　如果V到W之间的所有顶点都不同，则称简单路径
回路：起点等于终点的路径

　　

一.邻接矩阵

图的邻接矩阵存储方式就是用一个二维数组来表示。

邻接矩阵G[N][N]——N个顶点从0到N-1编号

顶点i、j有边，则G[i][j] = 1 或边的权重

　　

邻接矩阵的优点

　　直观、简单、好理解
　　方便检查任意一对顶点间是否存在边
　　方便找任一顶点的所有“邻接点”（有边直接相连的顶点）
　　方便计算任一顶点的“度”（从该点发出的边数为“出度”，指向该点的边数为“入度”）
　　无向图：对应行（或列）非0元素的个数
　　有向图：对应行非0元素的个数是“出度”；对应列非0元素的个数是“入度”

邻接矩阵的缺点

　　浪费空间—— 存稀疏图（点很多而边很少）有大量无效元素
　　　　对稠密图（特别是完全图）还是很合算的
　　　　浪费时间—— 统计稀疏图中一共有多少条边

 /* ͼµÄÁÚ½Ó¾ØÕó±íʾ·¨ */
 #include <iostream>
 #include <cstdio>
 #include <cstdlib>
 #include <queue>
 using namespace std;

 #define MaxVertexNum 100    /* ×î´ó¶¥µãÊýÉèΪ100 */
 #define INFINITY 65535        /* ÉèΪ˫×Ö½ÚÎÞ·ûºÅÕýÊýµÄ×î´óÖµ65535*/
 typedef int Vertex;         /* Óö¥µãϱê±íʾ¶¥µã,ΪÕûÐÍ */
 typedef int WeightType;        /* ±ßµÄȨֵÉèΪÕûÐÍ */
 typedef char DataType;        /* ¶¥µã´æ´¢µÄÊý¾ÝÀàÐÍÉèΪ×Ö·ûÐÍ */

 /* ±ßµÄ¶¨Òå */
 typedef struct ENode *PtrToENode;
 struct ENode{
     Vertex V1, V2;      /* ÓÐÏò±ß<V1, V2> */
     WeightType Weight;  /* ȨÖØ */
 };
 typedef PtrToENode Edge;

 /* ͼ½áµãµÄ¶¨Òå */
 typedef struct GNode *PtrToGNode;
 struct GNode{
     int Nv;  /* ¶¥µãÊý */
     int Ne;  /* ±ßÊý   */
     WeightType G[MaxVertexNum][MaxVertexNum]; /* ÁÚ½Ó¾ØÕó */
     DataType Data[MaxVertexNum];      /* ´æ¶¥µãµÄÊý¾Ý */
     /* ×¢Ò⣺ºÜ¶àÇé¿öÏ£¬¶¥µãÎÞÊý¾Ý£¬´ËʱData[]¿ÉÒÔ²»ÓóöÏÖ */
 };
 typedef PtrToGNode MGraph; /* ÒÔÁÚ½Ó¾ØÕó´æ´¢µÄͼÀàÐÍ */
 bool Visited[MaxVertexNum] = {false};

 MGraph CreateGraph( int VertexNum );
 void InsertEdge( MGraph Graph, Edge E );
 MGraph BuildGraph();
 bool IsEdge( MGraph Graph, Vertex V, Vertex W );
 void InitVisited();
 Vertex BFS ( MGraph Graph, Vertex S, void (*Visit)(Vertex) );
 Vertex DFS ( MGraph Graph, Vertex S, void (*Visit)(Vertex) );
 Vertex listDFS( MGraph Graph, void (*Visit)(Vertex) );
 void DFSListComponents( MGraph Graph, void (*Visit)(Vertex) );
 void BFSListComponents( MGraph Graph, void (*Visit)(Vertex) ); 

 MGraph CreateGraph( int VertexNum )
 { /* ³õʼ»¯Ò»¸öÓÐVertexNum¸ö¶¥µãµ«Ã»ÓбߵÄͼ */
     Vertex V, W;
     MGraph Graph;

     Graph = (MGraph)malloc(sizeof(struct GNode)); /* ½¨Á¢Í¼ */
     Graph->Nv = VertexNum;
     Graph->Ne = ;
     /* ³õʼ»¯ÁÚ½Ó¾ØÕó */
     /* ×¢Ò⣺ÕâÀïĬÈ϶¥µã±àºÅ´Ó0¿ªÊ¼£¬µ½(Graph->Nv - 1) */
     for (V=; V<Graph->Nv; V++)
         for (W=; W<Graph->Nv; W++)
             Graph->G[V][W] = INFINITY;

     return Graph;
 }

 void InsertEdge( MGraph Graph, Edge E )
 {
      /* ²åÈë±ß <V1, V2> */
      Graph->G[E->V1][E->V2] = E->Weight;
      /* ÈôÊÇÎÞÏòͼ£¬»¹Òª²åÈë±ß<V2, V1> */
      Graph->G[E->V2][E->V1] = E->Weight;
 }

 MGraph BuildGraph()
 {
     MGraph Graph;
     Edge E;
     Vertex V;
     int Nv, i;

     scanf("%d", &Nv);   /* ¶ÁÈ붥µã¸öÊý */
     Graph = CreateGraph(Nv); /* ³õʼ»¯ÓÐNv¸ö¶¥µãµ«Ã»ÓбߵÄͼ */ 

     scanf("%d", &(Graph->Ne));   /* ¶ÁÈë±ßÊý */
     if ( Graph->Ne !=  ) { /* Èç¹ûÓÐ±ß */
         E = (Edge)malloc(sizeof(struct ENode)); /* ½¨Á¢±ß½áµã */
         /* ¶ÁÈë±ß£¬¸ñʽΪ"Æðµã ÖÕµã ȨÖØ"£¬²åÈëÁÚ½Ó¾ØÕó */
         for (i=; i<Graph->Ne; i++) {
             scanf("%d %d %d", &E->V1, &E->V2, &E->Weight);
             /* ×¢Ò⣺Èç¹ûȨÖز»ÊÇÕûÐÍ£¬WeightµÄ¶ÁÈë¸ñʽҪ¸Ä */
             InsertEdge( Graph, E );
         }
     } 

     /* Èç¹û¶¥µãÓÐÊý¾ÝµÄ»°£¬¶ÁÈëÊý¾Ý */
     for (V=; V<Graph->Nv; V++)
         scanf(" %c", &(Graph->Data[V]));

     return Graph;
 }
 /* ÁÚ½Ó¾ØÕó´æ´¢µÄͼ - BFS */

 /* IsEdge(Graph, V, W)¼ì²é<V, W>ÊÇ·ñͼGraphÖеÄÒ»Ìõ±ß£¬¼´WÊÇ·ñVµÄÁڽӵ㡣  */
 /* ´Ëº¯Êý¸ù¾ÝͼµÄ²»Í¬ÀàÐÍÒª×ö²»Í¬µÄʵÏÖ£¬¹Ø¼üÈ¡¾öÓÚ¶Ô²»´æÔڵıߵıíʾ·½·¨¡£*/
 /* ÀýÈç¶ÔÓÐȨͼ, Èç¹û²»´æÔڵı߱»³õʼ»¯ÎªINFINITY, Ôòº¯ÊýʵÏÖÈçÏÂ:         */
 bool IsEdge( MGraph Graph, Vertex V, Vertex W )
 {
     return Graph->G[V][W]<INFINITY ? true : false;
 }

 //³õʼ»¯ Visited[] = false
 void InitVisited()
 {
     for(int i = ; i < MaxVertexNum; i++)
         Visited[i] = false;
 } 

 void Visit(Vertex v)
 {
     printf("%d ",v);
 }

 /* Visited[]Ϊȫ¾Ö±äÁ¿£¬ÒѾ­³õʼ»¯Îªfalse */
 Vertex BFS ( MGraph Graph, Vertex S, void (*Visit)(Vertex) )
 {   /* ÒÔSΪ³ö·¢µã¶ÔÁÚ½Ó¾ØÕó´æ´¢µÄͼGraph½øÐÐBFSËÑË÷ */
     queue<Vertex> Q;
     Vertex V, W;

     /* ·ÃÎʶ¥µãS£º´Ë´¦¿É¸ù¾Ý¾ßÌå·ÃÎÊÐèÒª¸Äд */
     Visit( S );
     Visited[S] = true; /* ±ê¼ÇSÒÑ·ÃÎÊ */
     Q.push(S); /* SÈë¶ÓÁÐ */

     while ( !Q.empty() ) {
         V = Q.front();
         Q.pop();      /* µ¯³öV */
         for( W=; W < Graph->Nv; W++ ) /* ¶ÔͼÖеÄÿ¸ö¶¥µãW */
             /* ÈôWÊÇVµÄÁڽӵ㲢ÇÒδ·ÃÎʹý */
             if ( !Visited[W] && IsEdge(Graph, V, W) ) {
                 /* ·ÃÎʶ¥µãW */
                 Visit( W );
                 Visited[W] = true; /* ±ê¼ÇWÒÑ·ÃÎÊ */
                 Q.push(W); /* WÈë¶ÓÁÐ */
             }
     } /* while½áÊø*/
     //ÒÑÓà BFSListComponents( MGraph Graph, void (*Visit)(Vertex) )½øÐиĽø
 //    printf("\n");
 //
 //    //±éÀú Visited[]ÁгöËùÓÐBFSµÄ¶¥µã ÈôÖ»ÐèÒ»¸ö¶¥µã¿ªÊ¼µÄBFS¿ÉºöÂÔ
 //    Vertex i;
 //    for(i = 0; i < Graph->Nv; i++) {
 //        if(Visited[i] == false)//ÕÒ³öδ±»·ÃÎʹýµÄ½áµã¼Ç¼iÖµ
 //            break;
 //    }
 //    if(i == Graph->Nv)
 //        return 0;
 //    else
 //        return BFS(Graph,i,Visit);
 }

 /* ÒÔSΪ³ö·¢µã¶ÔÁÚ½Ó¾ØÕó´æ´¢µÄͼGraph½øÐÐDFSËÑË÷ */
 Vertex DFS ( MGraph Graph, Vertex S, void (*Visit)(Vertex) )
 {
     Visited[S] = true;
     Visit(S);
     for(Vertex w = ; w < Graph->Nv; w++) {
         if( IsEdge(Graph, S, w) && Visited[w]==false) {
             DFS(Graph,w,Visit);
         }
     }
 }
 //ÁгöDFSµÄËùÓж¥µã ÒÑÓÃDFSListComponents( MGraph Graph, void (*Visit)(Vertex) )½øÐиĽø
 Vertex listDFS( MGraph Graph, void (*Visit)(Vertex) )
 {
     Vertex i;
     for(i = ; i < Graph->Nv; i++) {
         if(Visited[i] == false)//ÕÒ³öδ±»·ÃÎʹýµÄ½áµã¼Ç¼iÖµ
             break;
     }
     if(i == Graph->Nv)
         return ;
     DFS(Graph, i, Visit);
     printf("\n");

     return listDFS(Graph,Visit);
 }
 void DFSListComponents( MGraph Graph, void (*Visit)(Vertex) )
 {
     for(Vertex i = ; i < Graph->Nv; i++) {
         if(Visited[i] == false) {
             DFS(Graph, i, Visit);
             printf("\n");
         }
     }
 }
 void BFSListComponents( MGraph Graph, void (*Visit)(Vertex) )
 {
     for(Vertex i = ; i < Graph->Nv; i++) {
         if(Visited[i] == false) {
             BFS(Graph, i, Visit);
             printf("\n");
         }
     }
 }

 int main()
 {
     MGraph graph;
     graph = BuildGraph();
     InitVisited();
     listDFS(graph,&Visit);
     InitVisited();
     DFSListComponents(graph,&Visit);
     InitVisited();
 //    BFS(graph,0,&Visit);
     BFSListComponents(graph,&Visit);
     return ;
 } 

sj5_0 图的邻接矩阵

二.邻接表

G[N]为指针数组，对应矩阵每行一个链表，只存非0元素。

邻接表的优点
　　方便找任一顶点的所有“邻接点”
　　节约稀疏图的空间
　　需要N个头指针+ 2E个结点（每个结点至少2个域）
　　方便计算任一顶点的“度”？
　　　　对无向图：是的
　　　　对有向图：只能计算“出度”；需要构造“逆邻接表”（存指向自己的边）来方便计算“入度”

邻接表的缺点

　　不方便检查任意一对顶点间是否存在边

 /* 图的邻接表表示法 */
 //build用的 头插法 尾插法遍历 出来不同 但无影响
 #include <iostream>
 #include <cstdio>
 #include <cstdlib>
 #include <queue>
 using namespace std;

 #define MaxVertexNum 100    /* 最大顶点数设为100 */
 typedef int Vertex;         /* 用顶点下标表示顶点,为整型 */
 typedef int WeightType;        /* 边的权值设为整型 */
 typedef char DataType;        /* 顶点存储的数据类型设为字符型 */

 /* 边的定义 */
 typedef struct ENode *PtrToENode;
 struct ENode{
     Vertex V1, V2;      /* 有向边<V1, V2> */
     WeightType Weight;  /* 权重 */
 };
 typedef PtrToENode Edge;

 /* 邻接点的定义 */
 typedef struct AdjVNode *PtrToAdjVNode;
 struct AdjVNode{
     Vertex AdjV;        /* 邻接点下标 */
     WeightType Weight;  /* 边权重 */
     PtrToAdjVNode Next;    /* 指向下一个邻接点的指针 */
 };

 /* 顶点表头结点的定义 */
 typedef struct Vnode{
     PtrToAdjVNode FirstEdge;/* 边表头指针 */
     DataType Data;            /* 存顶点的数据 */
     /* 注意：很多情况下，顶点无数据，此时Data可以不用出现 */
 } AdjList[MaxVertexNum];    /* AdjList是邻接表类型 */

 /* 图结点的定义 */
 typedef struct GNode *PtrToGNode;
 struct GNode{
     int Nv;     /* 顶点数 */
     int Ne;     /* 边数   */
     AdjList G;  /* 邻接表 */
 };
 typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */
 bool Visited[MaxVertexNum] = {false}; 

 LGraph CreateGraph( int VertexNum );
 void InsertEdge( LGraph Graph, Edge E );
 LGraph BuildGraph();
 void Visit( Vertex V );
 void InitVisited();
 void DFS( LGraph Graph, Vertex V, void (*Visit)(Vertex) );
 Vertex listDFS( LGraph Graph, void (*Visit)(Vertex) );
 int BFS( LGraph Graph, Vertex V, void (*Visit)(Vertex) );
 void DFSListComponents( LGraph Graph, void (*Visit)(Vertex) );
 void BFSListComponents( LGraph Graph, void (*Visit)(Vertex) );

 LGraph CreateGraph( int VertexNum )
 { /* 初始化一个有VertexNum个顶点但没有边的图 */
     Vertex V;
     LGraph Graph;

     Graph = (LGraph)malloc( sizeof(struct GNode) ); /* 建立图 */
     Graph->Nv = VertexNum;
     Graph->Ne = ;
     /* 初始化邻接表头指针 */
     /* 注意：这里默认顶点编号从0开始，到(Graph->Nv - 1) */
        for (V=; V<Graph->Nv; V++)
         Graph->G[V].FirstEdge = NULL;

     return Graph;
 }

 void InsertEdge( LGraph Graph, Edge E )
 {
     PtrToAdjVNode NewNode;

     /* 插入边 <V1, V2> */
     /* 为V2建立新的邻接点 */
     NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
     NewNode->AdjV = E->V2;
     NewNode->Weight = E->Weight;
     /* 将V2插入V1的表头 */
     NewNode->Next = Graph->G[E->V1].FirstEdge;
     Graph->G[E->V1].FirstEdge = NewNode;

     /* 若是无向图，还要插入边 <V2, V1> */
     /* 为V1建立新的邻接点 */
     NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
     NewNode->AdjV = E->V1;
     NewNode->Weight = E->Weight;
     /* 将V1插入V2的表头 */
     NewNode->Next = Graph->G[E->V2].FirstEdge;
     Graph->G[E->V2].FirstEdge = NewNode;
 }

 LGraph BuildGraph()
 {
     LGraph Graph;
     Edge E;
     Vertex V;
     int Nv, i;

     scanf("%d", &Nv);   /* 读入顶点个数 */
     Graph = CreateGraph(Nv); /* 初始化有Nv个顶点但没有边的图 */ 

     scanf("%d", &(Graph->Ne));   /* 读入边数 */
     if ( Graph->Ne !=  ) { /* 如果有边 */
         E = (Edge)malloc( sizeof(struct ENode) ); /* 建立边结点 */
         /* 读入边，格式为"起点 终点 权重"，插入邻接矩阵 */
         for (i=; i<Graph->Ne; i++) {
             scanf("%d %d %d", &E->V1, &E->V2, &E->Weight);
             /* 注意：如果权重不是整型，Weight的读入格式要改 */
             InsertEdge( Graph, E );
         }
     } 

     /* 如果顶点有数据的话，读入数据 */
     for (V=; V<Graph->Nv; V++)
         scanf(" %c", &(Graph->G[V].Data));

     return Graph;
 }

 void Visit( Vertex V )
 {
     printf("%d ", V);
 }

 //初始化 Visited[] = false
 void InitVisited()
 {
     for(int i = ; i < MaxVertexNum; i++)
         Visited[i] = false;
 }  

 /* Visited[]为全局变量，已经初始化为false */
 void DFS( LGraph Graph, Vertex V, void (*Visit)(Vertex) )
 {   /* 以V为出发点对邻接表存储的图Graph进行DFS搜索 */
     PtrToAdjVNode W;

     Visit( V ); /* 访问第V个顶点 */
     Visited[V] = true; /* 标记V已访问 */

     for( W=Graph->G[V].FirstEdge; W; W=W->Next ) /* 对V的每个邻接点W->AdjV */
         if ( !Visited[W->AdjV] )    /* 若W->AdjV未被访问 */
             DFS( Graph, W->AdjV, Visit );    /* 则递归访问之 */
 }
 //已用InitVisited();进行改进
 Vertex listDFS( LGraph Graph, void (*Visit)(Vertex) )
 {
     Vertex i;
     for(i = ; i < Graph->Nv; i++) {
         if(Visited[i] == false)//找出未被访问过的结点记录i值
             break;
     }
     if(i == Graph->Nv)
         return ;
     DFS(Graph, i, Visit);
     printf("\n");
     return listDFS(Graph,Visit);
 }
 //图不连通时 列出各连通分量
 void DFSListComponents( LGraph Graph, void (*Visit)(Vertex) )
 {
     for(Vertex i = ; i < Graph->Nv; i++) {
         if(Visited[i] == false) {
             DFS(Graph, i, Visit);
             printf("\n");
         }
     }
 }
 int BFS( LGraph Graph, Vertex V, void (*Visit)(Vertex) )
 {
     queue<Vertex> Q;
     Vertex W;

     Visit( V ); /* 访问第V个顶点 */
     Visited[V] = true; /* 标记V已访问 */
     Q.push(V);

     while( !Q.empty() ) {
         W = Q.front();
         Q.pop();
         for(PtrToAdjVNode tempV = Graph->G[W].FirstEdge; tempV; tempV=tempV->Next ) /* 对W的每个邻接点tempV->AdjV */
             if( !Visited[tempV->AdjV]) {
                 Visited[tempV->AdjV] = true;
                 Visit(tempV->AdjV);
                 Q.push(tempV->AdjV);
             }
     }
     //已用 BFSListComponents进行改进
 //    printf("\n");
 //
 //    //遍历 Visited[]列出所有BFS的顶点 若只需一个顶点开始的BFS可忽略
 //    Vertex i;
 //    for(i = 0; i < Graph->Nv; i++) {
 //        if(Visited[i] == false)//找出未被访问过的结点记录i值
 //            break;
 //    }
 //    if(i == Graph->Nv)
 //        return 0;
 //    else
 //        return BFS(Graph,i,Visit);
     return ;
 }
 //图不连通时 列出各连通分量
 void BFSListComponents( LGraph Graph, void (*Visit)(Vertex) )
 {
     for(Vertex i = ; i < Graph->Nv; i++) {
         if(Visited[i] == false) {
             BFS(Graph, i, Visit);
             printf("\n");
         }
     }
 }

 int main()
 {
     LGraph graph;
     graph = BuildGraph();
     InitVisited();
     listDFS(graph,&Visit);
     InitVisited();
     DFSListComponents(graph,&Visit);
     InitVisited();
 //    BFS(graph, 0, &Visit);
     BFSListComponents(graph,&Visit);
     return ;
 }

sj5_1 图的邻接表

三.BFS广度优先搜索(Breadth First Search, BFS)

运用队列，将顶点V的每个邻接点进队。(类似于树的层先遍历)

若有N个顶点、E条边，时间复杂度是

　　用邻接表存储图，有O(N+E)
　　用邻接矩阵存储图，有O(N^2)

四.DFS深度优先搜索索(Depth First Search, DFS)

用递归(类似于树的先序遍历)。

ListComponents 图不连通时，列出各连通分量。

若有N个顶点、E条边，时间复杂度是

　　用邻接表存储图，有O(N+E)
　　用邻接矩阵存储图，有O(N^2)

五.最短路径

　　两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径

　　　　第一个顶点为源点(Source)

　　　　最后一个顶点为终点(Destination)

单源最短路径问题：从某固定源点出发，求其到所有其他顶点的最短路径

无权图(无论是否有向)：按照路径长度递增（非递减）的顺序找出到各个顶点的最短路

类似于BFS，运用队列

dist[W] = S到W最短距离

dist[S] = 0;

path[W] = S到W路上经过的顶点

时间复杂度T = O(V + E)

 /* dist[]和path[]全部初始化为-1 */
 void Unweighted ( LGraph Graph, int dist[], int path[], Vertex S )
 {
     queue<Vertex> Q;
     Vertex V;
     PtrToAdjVNode W;

     dist[S] = ; /* 初始化源点 */
     Q.push(S);

     while( !Q.empty() ){
         V = Q.front();
         Q.pop();
         for ( W = Graph->G[V].FirstEdge; W; W = W->Next ) /* 对V的每个邻接点W->AdjV */
             if ( dist[W->AdjV] == - ) { /* 若W->AdjV未被访问过 */
                 dist[W->AdjV] = dist[V] + ; /* W->AdjV到S的距离更新 */
                 path[W->AdjV] = V; /* 将V记录在S到W->AdjV的路径上 */
                 Q.push(W->AdjV);
             }
     } /* while结束*/
 }

有权图(无论是否有向):按照递增的顺序找出到各个顶点的最短路

Dijkstra 算法

　　令S={源点s + 已经确定了最短路径的顶点vi}

　　对任一未收录的顶点v，定义dist[v]为s到v的最短路径长度，但该路径仅经过S中的顶点。即路径{s-->(vi∈S)-->v}的最小长度

　　路径是按照递增（非递减）的顺序生成的，则

　　　　 真正的最短路必须只经过S中的顶点(!!!) 因为是递增的顺序生成 如果顶点w不再路径集合上 然而是最短，应该早就收录了(意会。。。)

　　　　 每次从未收录的顶点中选一个dist最小的收录（贪心）

　　　　 增加一个v进入S，可能影响另外一个w的dist值！(如果收录v使得s到w的路径变短，则s到w的路径一定经过v，并且v到w有一条边)

　　　　　　dist[w] = min{dist[w], dist[v] + <v,w>的权重}

　白话算法：

　每次找到dist最小的值，即第一次找到S和第二个顶点dist最小的那个，　　　　          比较更新该顶点未访问过的邻接点的dist　　　　       　　　　　　　　　　              然后一直找dist最小的

　　

　　不能有负值圈

图只更新dist[]中的值 不改变邻接矩阵的值！

 /* 邻接矩阵存储 - 有权图的单源最短路算法 */
 Vertex FindMinDist( MGraph Graph, int dist[], int collected[] )
 { /* 返回未被收录顶点中dist最小者 */
     Vertex MinV, V;
     int MinDist = INFINITY;

     for (V=; V<Graph->Nv; V++) {
         if ( collected[V]==false && dist[V] < MinDist) {
             /* 若V未被收录，且dist[V]更小 */
             MinDist = dist[V]; /* 更新最小距离 */
             MinV = V; /* 更新对应顶点 */
         }
     }
     if (MinDist < INFINITY) /* 若找到最小dist */
         return MinV; /* 返回对应的顶点下标 */
     else return ERROR;  /* 若这样的顶点不存在，返回错误标记 */
 }

 bool Dijkstra( MGraph Graph, int dist[], int path[], Vertex S )
 {
     int collected[MaxVertexNum];
     Vertex V, W;

     /* 初始化：此处默认邻接矩阵中不存在的边用INFINITY表示 */
     for ( V=; V < Graph->Nv; V++ ) {
         dist[V] = Graph->G[S][V];
         path[V] = -;
         collected[V] = false;
     }
     /* 先将起点收入集合 */
     dist[S] = ;
     collected[S] = true;

     while () {
         /* V = 未被收录顶点中dist最小者 */
         V = FindMinDist( Graph, dist, collected );
         if ( V==ERROR ) /* 若这样的V不存在 */
             break;      /* 算法结束 */
         collected[V] = true;  /* 收录V */
         for( W = ; W < Graph->Nv; W++ ) /* 对图中的每个顶点W */
             /* 若W是V的邻接点并且未被收录 */
             if ( collected[W]==false && Graph->G[V][W]<INFINITY ) {
                 if ( Graph->G[V][W]< ) /* 若有负边 */
                     return false; /* 不能正确解决，返回错误标记 */
                 /* 若收录V使得dist[W]变小 */
                 if ( dist[V]+Graph->G[V][W] < dist[W] ) {
                     dist[W] = dist[V] + Graph->G[V][W]; /* 更新dist[W] */
                     path[W] = V; /* 更新S到W的路径 */
                 }
             }
     } /* while结束*/
     return true; /* 算法执行完毕，返回正确标记 */
 }

关于找最小dist

　　①直接扫描所有未收录顶点-O(V)

　　　　T=O(V^2+E)   --->对于稠密图效果好

　　②将dist存在最小堆中-O(logV)

　　　　更新dist(W)的值-O(logV)

　　　　T = O(VlogV+ElogV) = O(ElogV)    --->对于稠稀疏图效果好

多源最短路径问题：求任意两顶点间的最短路径

方法一：直接将单源最短路算法调用V遍

　　　　T = O(V^3 + E*V)   --->对于稀疏图效果好

方法二：Floyd算法　　--->对于稠密图效果好

　　　　T = O(V^3)

Floyd 算法

　　Dk[i][j] = 路径{ i -> { l ≤ k } -> j }的最小长度

　　D0, D1, …, D|V|-1[i][j]即给出了i到j的真正最短距离

　　最初的D-1是邻接矩阵

　　当Dk-1已经完成，递推到Dk时：

　　　　或者k ∉最短路径{ i -> { l ≤ k } -> j }，则Dk = Dk-1

　　　　或者k ∈最短路径{ i -> { l ≤ k } -> j }，则该路径必定由两段最短路径组成： Dk[i][j]=Dk-1[i][k]+Dk-1[k][j]

 /* 邻接矩阵存储 - 多源最短路算法 */

 bool Floyd( MGraph Graph, WeightType D[][MaxVertexNum], Vertex path[][MaxVertexNum] )
 {
     Vertex i, j, k;

     /* 初始化 */
     for ( i=; i<Graph->Nv; i++ )
         for( j=; j<Graph->Nv; j++ ) {
             D[i][j] = Graph->G[i][j];
             path[i][j] = -;
         }

     for( k=; k<Graph->Nv; k++ )
         for( i=; i<Graph->Nv; i++ )
             for( j=; j<Graph->Nv; j++ )
                 if( D[i][k] + D[k][j] < D[i][j] ) {
                     D[i][j] = D[i][k] + D[k][j];
                     if ( i==j && D[i][j]< ) /* 若发现负值圈 */
                         return false; /* 不能正确解决，返回错误标记 */
                     path[i][j] = k;
                 }
     return true; /* 算法执行完毕，返回正确标记 */
 }