最短路径算法-ag真人游戏

3.2 c 实现

3.2.1. 基本定义

class matrixudg {
    #define max    100
    #define inf    (~(0x1<<31))        // 无穷大(即0x7fffffff)
    private:
        char mvexs[max];    // 顶点集合
        int mvexnum;             // 顶点数
        int medgnum;             // 边数
        int mmatrix[max][max];   // 邻接矩阵
    public:
        // 创建图(自己输入数据)
        matrixudg();
        // 创建图(用已提供的矩阵)
        //matrixudg(char vexs[], int vlen, char edges[][2], int elen);
        matrixudg(char vexs[], int vlen, int matrix[][9]);
        ~matrixudg();
        // 深度优先搜索遍历图
        void dfs();
        // 广度优先搜索（类似于树的层次遍历）
        void bfs();
        // prim最小生成树(从start开始生成最小生成树)
        void prim(int start);
        // 克鲁斯卡尔（kruskal)最小生成树
        void kruskal();
        // dijkstra最短路径
        void dijkstra(int vs, int vexs[], int dist[]);
        // 打印矩阵队列图
        void print();
    private:
        // 读取一个输入字符
        char readchar();
        // 返回ch在mmatrix矩阵中的位置
        int getposition(char ch);
        // 返回顶点v的第一个邻接顶点的索引，失败则返回-1
        int firstvertex(int v);
        // 返回顶点v相对于w的下一个邻接顶点的索引，失败则返回-1
        int nextvertex(int v, int w);
        // 深度优先搜索遍历图的递归实现
        void dfs(int i, int *visited);
        // 获取图中的边
        edata* getedges();
        // 对边按照权值大小进行排序(由小到大)
        void sortedges(edata* edges, int elen);
        // 获取i的终点
        int getend(int vends[], int i);
};

matrixudg是邻接矩阵对应的结构体。
mvexs用于保存顶点，mvexnum是顶点数，medgnum是边数；mmatrix则是用于保存矩阵信息的二维数组。例如，mmatrix[i][j]=1，则表示"顶点i(即mvexs[i])"和"顶点j(即mvexs[j])"是邻接点；mmatrix[i][j]=0，则表示它们不是邻接点。

3.2.2. 迪杰斯特拉算法

/*
 * dijkstra最短路径。
 * 即，统计图中"顶点vs"到其它各个顶点的最短路径。
 *
 * 参数说明：
 *       vs -- 起始顶点(start vertex)。即计算"顶点vs"到其它顶点的最短路径。
 *     prev -- 前驱顶点数组。即，prev[i]的值是"顶点vs"到"顶点i"的最短路径所经历的全部顶点中，位于"顶点i"之前的那个顶点。
 *     dist -- 长度数组。即，dist[i]是"顶点vs"到"顶点i"的最短路径的长度。
 */
void matrixudg::dijkstra(int vs, int prev[], int dist[])
{
    int i,j,k;
    int min;
    int tmp;
    int flag[max];      // flag[i]=1表示"顶点vs"到"顶点i"的最短路径已成功获取。
    // 初始化
    for (i = 0; i < mvexnum; i  )
    {
        flag[i] = 0;              // 顶点i的最短路径还没获取到。
        prev[i] = 0;              // 顶点i的前驱顶点为0。
        dist[i] = mmatrix[vs][i]; // 顶点i的最短路径为"顶点vs"到"顶点i"的权。
    }
    // 对"顶点vs"自身进行初始化
    flag[vs] = 1;
    dist[vs] = 0;
    // 遍历mvexnum-1次；每次找出一个顶点的最短路径。
    for (i = 1; i < mvexnum; i  )
    {
        // 寻找当前最小的路径；
        // 即，在未获取最短路径的顶点中，找到离vs最近的顶点(k)。
        min = inf;
        for (j = 0; j < mvexnum; j  )
        {
            if (flag[j]==0 && dist[j]
1. 邻接矩阵源码(matrix_udg.c)
2. 邻接表源码(list_udg.c)
############################################################
dijkstra算法
1.定义概览
dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。
问题描述：在无向图 g=(v,e) 中，假设每条边 e[i] 的长度为 w[i]，找到由顶点 v0 到其余各点的最短路径。（单源最短路径）
2.算法描述
1)算法思想：设g=(v,e)是一个带权有向图，把图中顶点集合v分成两组，第一组为已求出最短路径的顶点集合（用s表示，初始时s中只有一个源点，以后每求得一条最短路径 , 就将加入到集合s中，直到全部顶点都加入到s中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用u表示），按最短路径长度的递增次序依次把第二组的顶点加入s中。在加入的过程中，总保持从源点v到s中各顶点的最短路径长度不大于从源点v到u中任何顶点的最短路径长度。此外，每个顶点对应一个距离，s中的顶点的距离就是从v到此顶点的最短路径长度，u中的顶点的距离，是从v到此顶点只包括s中的顶点为中间顶点的当前最短路径长度。
2)算法步骤：
a.初始时，s只包含源点，即s＝{v}，v的距离为0。u包含除v外的其他顶点，即:u={其余顶点}，若v与u中顶点u有边，则正常有权值，若u不是v的出边邻接点，则权值为∞。
b.从u中选取一个距离v最小的顶点k，把k，加入s中（该选定的距离就是v到k的最短路径长度）。
c.以k为新考虑的中间点，修改u中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
d.重复步骤b和c直到所有顶点都包含在s中。
 
执行动画过程如下图
 
3.算法代码实现：
const int  maxint = 32767;
const int maxnum = 10;
int dist[maxnum];
int prev[maxnum];
int a[maxunm][maxnum];
void dijkstra(int v0)
{
  　　bool s[maxnum];                                  // 判断是否已存入该点到s集合中
      int n=maxnum;
  　　for(int i=1; i<=n;   i)
 　　 {
      　　dist[i] = a[v0][i];
      　　s[i] = false;                                // 初始都未用过该点
      　　if(dist[i] == maxint)    
            　　prev[i] = -1;
 　　     else 
            　　prev[i] = v0;
   　　}
   　 dist[v0] = 0;
   　 s[v0] = true; 　　
 　　 for(int i=2; i<=n; i  )
 　　 {
       　　int mindist = maxint;
       　　int u = v0; 　　                            // 找出当前未使用的点j的dist[j]最小值
      　　 for(int j=1; j<=n;   j)
      　　    if((!s[j]) && dist[j]
 
4.算法实例
先给出一个无向图
用dijkstra算法找出以a为起点的单源最短路径步骤如下
 
floyd算法
1.定义概览
floyd-warshall算法（floyd-warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。floyd-warshall算法的时间复杂度为o(n3)，空间复杂度为o(n2)。
 
2.算法描述
1)算法思想原理：
     floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要为这个目标重新做一个诠释（这个诠释正是动态规划最富创造力的精华所在）
      从任意节点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的最短路径的距离。
2).算法描述：
a.从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。 　　
b.对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。
3).floyd算法过程矩阵的计算----十字交叉法
方法：两条线，从左上角开始计算一直到右下角 如下所示
给出矩阵，其中矩阵a是邻接矩阵，而矩阵path记录u,v两点之间最短路径所必须经过的点
相应计算方法如下：
最后a3即为所求结果
 
3.算法代码实现
typedef struct          
{        
    char vertex[vertexnum];                                //顶点表         
    int edges[vertexnum][vertexnum];                       //邻接矩阵,可看做边表         
    int n,e;                                               //图中当前的顶点数和边数         
}mgraph; 
void floyd(mgraph g)
{
 　　int a[maxv][maxv];
 　　int path[maxv][maxv];
 　　int i,j,k,n=g.n;
 　　for(i=0;i(a[i][k] a[k][j]))
             　　{
                   　　a[i][j]=a[i][k] a[k][j];
                   　　path[i][j]=k;
              　 } 
    　} 
} 
算法时间复杂度:o(n3)