精华内容
下载资源
问答
  • 2018-06-04 09:56:33

    Dijkstra算法

    1.定义概览

    Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点(节点需为源点)到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法,注意该算法要求图中不存在负权边。

     实例:假设有A,B,C,D四个城市,(这里讨论的是有向网) 它们的距离为:  A->B(10),A->C(11),B->D(12),C->D(13);

    所谓単源路径就是解决从源点 A开始找出到其他城市的最短距离(除本身外的其他所有城市)。Dijkstra算法可以求出A->B(10),A->C(11),A->D(22);

    拓展2:多源最短路径(常用Floyd算法)是解决任意两点间的最短路径的一种算法,(不局限于从源点出发,到其他各个顶点 )可以正确处理有向图或负权的最短路径问题,同时也被用于计算有向图的传递闭包。Floyd算法的时间复杂度为O(N3),空间复杂度为O(N2)。

    代码

    [cpp]  view plain  copy
    1. /* 
    2.   @ Dijkstra算法(単源最短路径) 
    3. */  
    4. #include<iostream>  
    5. #include<cstdio>  
    6. #include<cstdlib>  
    7. #define MAXV 100  
    8. #define LIMITLESS 9999    //定义为无穷大,默认为节点间不存在联系  
    9. using namespace std;  
    10. typedef struct  
    11. {  
    12.    char info; //顶点其他信息  
    13. }VertexType;  
    14.   
    15. typedef struct MGraph  
    16. {  
    17.     int v;     //顶点数  
    18.     int e;    //边数  
    19.     int edges[MAXV][MAXV];//邻接矩阵的数组表现  
    20.     VertexType vexs[MAXV]; //顶点信息  
    21. }MGraph;  
    22.   
    23. void creat(MGraph *G)  
    24. {  
    25.     int i, j, k, w;  
    26.     int start, end;  
    27.     printf("请输入顶点数和边数:\n");  
    28.     scanf("%d%d", &(G->v), &(G->e));  
    29.     getchar();  
    30.     printf("请输入顶点信息:\n");  
    31.     for (i = 0; i<G->v; i++)  
    32.     {  
    33.         scanf("%c", &(G->vexs[i].info));  
    34.     }  
    35.     for (i = 0; i<G->v; i++)  
    36.     {  
    37.         for (j = 0; j<G->v; j++)  
    38.         {  
    39.             G->edges[i][j] = LIMITLESS;  
    40.         }  
    41.     }  
    42.     printf("输入图的顶点边的下标值和它的权值:\n");  
    43.     for (k = 0; k<G->e; k++)  
    44.     {  
    45.         scanf("%d%d%d", &start, &end, &w);  
    46.         G->edges[start][end] = w;  
    47.     }  
    48. }  
    49.   
    50. void print(MGraph *G)  
    51. {  
    52.     int i, j;  
    53.     printf("顶点数:%d,边数:%d\n", G->v, G->e);  
    54.     printf("%d个顶点的信息:\n", G->v);  
    55.     for (i = 0; i<G->v; i++)  
    56.     {  
    57.         printf("%5c",G->vexs[i].info);  
    58.     }  
    59.     printf("\n各个顶点的连接情况:\n");  
    60.     printf("\t");  
    61.     for (i = 0; i<G->v; i++)  
    62.     {  
    63.         printf("[%d]\t", i);  
    64.     }  
    65.     printf("\n");  
    66.     for (i = 0; i<G->v; i++)  
    67.     {  
    68.         printf("[%d]\t", i);  
    69.         for (j = 0; j<G->v; j++)  
    70.         {  
    71.             if (G->edges[i][j] == LIMITLESS)  
    72.             {  
    73.                 printf("oo\t");  
    74.             }  
    75.             else  
    76.             {  
    77.                 printf("%d\t", G->edges[i][j]);  
    78.             }  
    79.         }  
    80.         printf("\n");  
    81.     }  
    82. }  
    83.   
    84. void Ppath(MGraph *g,int path[], int i, int v) //前向递归查找路径上的顶点,但不包含起点与终点的路径值  
    85. {  
    86.     int k;  
    87.     k = path[i];  
    88.     if (k == v)   //无中间节点,退出  
    89.     {  
    90.         return;  
    91.     }  
    92.     Ppath(g,path, k, v);  
    93.     printf("%c",g->vexs[k]);  
    94. }  
    95.   
    96. void Dispath(MGraph *g,int dist[], int path[], int s[], int n, int v)  
    97. {  
    98.     int i;  
    99.     for (i = 0; i < n; i++)  
    100.     {  
    101.         if (s[i] == 1)  
    102.         {  
    103.             printf("从%c到%c的最短路径长度为:%d\t路径为:", g->vexs[v], g->vexs[i], dist[i]);  
    104.             printf("%c",g->vexs[v]);     //输出路径上的起点  
    105.             Ppath(g,path, i, v);  //输出路径上的中间点  
    106.             printf("%c\n",g->vexs[i]); //输出路径上的终点  
    107.         }  
    108.         else  
    109.         {  
    110.             printf("从%c到%c不存在路径\n", g->vexs[v], g->vexs[i]);  
    111.         }  
    112.     }  
    113. }  
    114.   
    115. void Dijkstra(MGraph *g, int v)  
    116. {  
    117.     int mindis, i, j, u;  
    118.     int s[MAXV];     //表示这个顶点是否存入最短路线中(0表示未加入,1表示已加入)  
    119.     int dist[MAXV]; //表示起始点到此顶点的距离  
    120.     int path[MAXV];//表示此点的上一步是哪一个顶点  
    121.     for (i = 0; i < g->v; i++)  
    122.     {  
    123.         s[i] = 0;  
    124.         dist[i] = g->edges[v][i];  
    125.         if (g->edges[v][i] < LIMITLESS)  
    126.         {  
    127.             path[i] = v;  
    128.         }  
    129.         else  
    130.         {  
    131.             path[i] = -1;  
    132.         }  
    133.     }  
    134.     s[v] = 1;  
    135.     path[v] = 0;  
    136.     for (i = 0; i < g->v; i++)  
    137.     {  
    138.         mindis = LIMITLESS;         //mindis置最小长度初值  
    139.         for (j = 0; j < g->v; j++) //选取不在s中且具有最小距离的顶点u  
    140.         {  
    141.             if (s[j] == 0 && dist[j] <mindis)  
    142.             {  
    143.                 mindis = dist[j];  
    144.                 u = j;  
    145.             }  
    146.         }  
    147.         s[u] = 1;  
    148.         for (j = 0; j < g->v; j++)  
    149.         {  
    150.             if (s[j] == 0)  
    151.             {  
    152.                 if (g->edges[u][j] < LIMITLESS&&dist[u] + g->edges[u][j] < dist[j])  
    153.                 {  
    154.                     dist[j] = dist[u] + g->edges[u][j];  
    155.                     path[j] = u;  
    156.                 }  
    157.             }  
    158.         }  
    159.     }  
    160.     Dispath(g ,dist, path, s, g->v, v);  
    161. }  
    162.   
    163. int main(void)  
    164. {  
    165.     MGraph *g;  
    166.     g = (MGraph *)malloc(sizeof(MGraph));  
    167.     creat(g);  
    168.     print(g);  
    169.     Dijkstra(g,0);  
    170.     return 0;  
    171. }  
    172.    
    更多相关内容
  • 本设计以VC++6.0作为程序开发环境,C语言作为程序开发语言,详细介绍了最短路径的求解算法及其C语言实现过程。系统主要实现了图的创建、单源点最短路径的计算功能。依照本系统可以解决实际生活中许多路径选择问题,...
  • Dijkstra算法C语言实现

    2018-04-29 16:40:28
    算法描述如下: 1)令arcs表示弧上的权值。若弧不存在,则置arcs为∞(在本程序中为MAXCOST)。S为已找到的从 出发的的终点的集合,初始状态为空集。那么,从 出发到图上其余各顶点 可能达到的长度的初值为D=arcs...
  • 能够实现 Dijkstra算法,内涵代码,运行即可实现
  • C语言实现Dijkstra算法

    2015-09-16 14:02:13
    本程序使用C语言实现了Dijkstra算法。程序中,定义好邻接矩阵,可以计算出任一节点到其他所有节点的最短路径,并打印路径与长度。其中对最短路径的存储是依据所得到的生成树,可以减少内存空间占用。
  • Dijkstra算法C语言实现(附图解)

    千次阅读 多人点赞 2020-05-10 20:28:23
    Dijkstra算法: 问题:给定一个带权图G=(V,E,w),找到从给定源点u0到其他各点的最短路径。 绿色顶点表示源点到该顶点的距离已确定 蓝色顶点表示要加入集合S的顶点 {dis,v},v表示前驱动点,dis表示源点到该顶点的最短...

    Dijkstra算法:
    问题:给定一个带权图G=(V,E,w),找到从给定源点u0到其他各点的最短路径。
    Step:
    求带权图G(V,E)的点v0到其他各点的最短路径;
    1.初始时,S={v0},U={v1,v1…vn};点v0到其他点的最短距离为<v0,vi>(i=1,2,3…n)的权;将v0到其他各点vi的最短路径中vi的前驱动点初始化为v0;
    2,从U中选取u,使得当前v0到u的最短路径的距离小于v0到U中其他各点的最短路径的距离,将u加入S,并将u从U中删除
    3,遍历每个在U中的点s,如果以u为中介点的最短路径的距离小于当前存储的距离,更新从v0到s的最短路径的距离,并将v0到s的最短路径的s的前驱动点更新为u;
    4,重复2,3直到U为空;

    在****这里插入图片描述
    绿色顶点表示源点到该顶点的距离已确定 蓝色顶点表示要加入集合S的顶点 {dis,v},v表示前驱动点,dis表示源点到该顶点的最短距离

    在这里插入图片描述
    在这里插入图片描述
    代码:

    #include <stdio.h>
    #define INF 10000000
    #define MaxSize 50
    int graph[MaxSize][MaxSize];  //MaxSize为最大顶点数
    int dis[MaxSize];             //dis[i]为源点到顶点i的最短距离
    int visit[MaxSize];            //visit[i]标记顶点i的最短路径是否已求出visit[i] == 1表示已求出
    int prevetrix[MaxSize];       //前驱动点
    void dij(int n)
    {    
        int count = 0;          //count是已求出最短路径的顶点数目
        visit[0] = 1;    
        prevetrix[0] = 0;    
        count++;    
        for (int i = 1; i < n; i++)    //初始化
        {        
            dis[i] = graph[0][i];        
            prevetrix[i] = 0;    
        }    
        while (count < n)    
        {        
            int min = INF, target_index;        
            for (int i = 1; i < n; i++)        
            {            
                if (visit[i] == 0 && min > dis[i])         //找到距离源点最短的顶点target_index
                {                
                    min = dis[i];                
                    target_index = i;            
                }        
            }        
            visit[target_index] = 1;        
            count++;        
            for (int i = 1; i < n; i++)        
            {            
                if (visit[i] == 0 && dis[target_index] + 
                graph[target_index][i] < dis[i])            //更新
                {                
                    dis[i] = dis[target_index] + graph[target_index][i];
                    prevetrix[i] = target_index;            
                }        
            }    
        }
    }
    int main()
    {    
        int n, m;    
        scanf("%d %d", &n, &m);    //n为顶点数,m为边数
        int a, b, w, path[n];    
        for (int i = 0; i < n; i++)    
        {        
            for (int j = 0; j < n; j++)        
            {            
                graph[i][j] = INF;        
            }    
        }    
        for (int i = 0; i < m; i++)    
        {        
            scanf("%d %d %d", &a, &b, &w);        //a为起始点,b为终点,w为边a->b的权重
            graph[a][b] = w;    
        }     
        dij(n);    
        printf("\n\n");    
        for (int i = 1; i < n; i++)    
        {        
            if (dis[i] == INF)        
            {            
                printf("顶点0到顶点%d没有最短路径\n", i);        
            }        
            else        
            {            
        	    printf("顶点0到顶点%d有长为%d的最短路径:", i,dis[i]);            
        	    int cur = i, index = 0;            
                path[index] = cur;            
                while (1)            
                {                
                    path[index + 1] = prevetrix[path[index]];                
                    if (path[index + 1] == 0)                    
                        break;                
                    index++;            
                }            
                for (int j = index + 1; j > 0; j--)            
                {                
                    printf("%d->", path[j]);            
                }            
                printf("%d\n", path[0]);        
            }    
        }
    }
    
    输入:
    6 8
    0 2 10
    0 4 30
    0 5 100
    1 2 5
    2 3 50
    3 5 10
    4 5 60
    4 3 20
    输出:
    顶点0到顶点1没有最短路径
    顶点0到顶点2有长为10的最短路径:0->2
    顶点0到顶点3有长为50的最短路径:0->4->3
    顶点0到顶点4有长为30的最短路径:0->4
    顶点0到顶点5有长为60的最短路径:0->4->3->5
    

    注意:diskstra算法只能求边权值为非负值的情况

    展开全文
  • 输入各结点构成的邻接矩阵及开始结点,计算出该节点到其他各节点之间的最短距离。也可计算某一开始结点到指定结点的最短距离。
  • 程序采用读.dat文件的方式,获得顶点和弧,设置菜单栏,可供循环使用。
  • Dijkstra算法c语言程序

    2018-04-25 15:51:10
    该程序为Dijkstra算法的的c语言程序,Dijkstra算法一般指迪杰斯特拉算法。迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法,是从一个顶点到其余各顶点的最短路径算法,解决的...
  • 以前也零零碎碎发过一些排序算法,但排版都不太好,又重新整理一次,排序算法是数据结构的重要部分,系统地学习很有必要。时间、空间复杂度比较| 排序算法 | 平均时间复杂度 | 最差时间复杂度 | 空间复杂度 | 数据...

    3ec2a5088eb7f8bbe402fce0526596f1.png

    以前也零零碎碎发过一些排序算法,但排版都不太好,又重新整理一次,排序算法是数据结构的重要部分,系统地学习很有必要。

    时间、空间复杂度比较

    | 排序算法 | 平均时间复杂度 | 最差时间复杂度 | 空间复杂度 | 数据对象稳定性 |

    | --- | --- | --- | --- | --- |

    | 冒泡排序 | O(n2) | O(n2) | O(1) | 稳定 |

    | 选择排序 | O(n2) | O(n2) | O(1) | 数组不稳定、链表稳定 |

    | 插入排序 | O(n2) | O(n2) | O(1) | 稳定 |

    | 快速排序 | O(n*log2n) | O(n2) | O(log2n) | 不稳定 |

    | 堆排序 | O(n*log2n) | O(n*log2n) | O(1) | 不稳定 |

    | 归并排序 | O(n*log2n) | O(n*log2n) | O(n) | 稳定 |

    | 希尔排序 | O(n*log2n) | O(n2) | O(1) | 不稳定 |

    | 计数排序 | O(n+m) | O(n+m) | O(n+m) | 稳定 |

    | 桶排序 | O(n) | O(n) | O(m) | 稳定 |

    | 基数排序 | O(k*n) | O(n2) |

    | 稳定 |

    1 冒泡排序

    算法思想

    1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
    2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
    3. 针对所有的元素重复以上的步骤,除了最后一个。
    4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

    259f378090e4a03e9850828ec8d5b26f.gif


    代码:

    void bubbleSort(int a[], int n)
    {
      for(int i =0 ; i< n-1; ++i)
      {
        for(int j = 0; j < n-i-1; ++j)
        {
          if(a[j] > a[j+1])
          {
            int tmp = a[j] ;  //交换
            a[j] = a[j+1] ;
            a[j+1] = tmp;
          }
        }
      }
    }

    https://jq.qq.com/?_wv=1027&k=9ePUlzmV

    2 选择排序

    算法思想

    1. 在未排序序列中找到最小(大)元素,存放到排序序列的起始位置
    2. 从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾
    3. 以此类推,直到所有元素均排序完毕

    8536dd715faaba55efcb2bf8b56e2828.png


    代码:

    function selectionSort(arr) {
        var len = arr.length;
        var minIndex, temp;
        for (var i = 0; i < len - 1; i++) {
            minIndex = i;
            for (var j = i + 1; j < len; j++) {
                if (arr[j] < arr[minIndex]) {     // 寻找最小的数
                    minIndex = j;                 // 将最小数的索引保存
                }
            }
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        return arr;
    }

    3 插入排序

    算法思想

    1. 从第一个元素开始,该元素可以认为已经被排序
    2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
    3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
    4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
    5. 将新元素插入到该位置后
    6. 重复步骤2~5

    33d454d9c1efc074c106ebd2457e4602.gif

    代码:

    void print(int a[], int n ,int i){
      cout<<i <<":";
      for(int j= 0; j<8; j++){
        cout<<a[j] <<" ";
      }
      cout<<endl;
    }
    void InsertSort(int a[], int n)
    {
      for(int i= 1; i<n; i++){
        if(a[i] < a[i-1]){   //若第i个元素大于i-1元素,直接插入。小于的话,移动有序表后插入
          int j= i-1;
          int x = a[i];     //复制为哨兵,即存储待排序元素
          a[i] = a[i-1];           //先后移一个元素
          while(x < a[j]){   //查找在有序表的插入位置
            a[j+1] = a[j];
            j--;     //元素后移
          }
          a[j+1] = x;     //插入到正确位置
        }
        print(a,n,i);      //打印每趟排序的结果
      }
    
    }
    
    int main(){
      int a[15] = {2,3,4,5,15,19,16,27,36,38,44,46,47,48,50};
      InsertSort(a,15);
      print(a,15,15);
    }

    4 快速排序

    算法思想

    1. 选取第一个数为基准
    2. 将比基准小的数交换到前面,比基准大的数交换到后面
    3. 对左右区间重复第二步,直到各区间只有一个数

    081f053750b37bfc667ed73881d930c2.gif


    代码:

    void QuickSort(vector<int>& v, int low, int high) {
    if (low >= high)// 结束标志
    return;
    int first = low;// 低位下标
    int last = high;// 高位下标
    int key = v[first];// 设第一个为基准
    
    while (first < last)
    {
    // 将比第一个小的移到前面
    while (first < last && v[last] >= key)
    last--;
    if (first < last)
    v[first++] = v[last];
    
    // 将比第一个大的移到后面
    while (first < last && v[first] <= key)
    first++;
    if (first < last)
    v[last--] = v[first];
    }
    //
    v[first] = key;
    // 前半递归
    QuickSort(v, low, first - 1);
    // 后半递归
    QuickSort(v, first + 1, high);
    }

    5 堆排序

    堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

    算法思想

    1. 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆,此堆为初始的无序区;
    2. 将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n];
    3. 由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。

    代码:

    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    // 堆排序:(最大堆,有序区)。从堆顶把根卸出来放在有序区之前,再恢复堆。
    
    void max_heapify(int arr[], int start, int end) {
    //建立父节点指标和子节点指标
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) { //若子节点在范围内才做比较
    if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点指标,选择最大的
    son++;
    if (arr[dad] > arr[son]) //如果父节点大于子节点代表调整完成,直接跳出函数
    return;
    else { //否则交换父子內容再继续子节点与孙节点比較
    swap(arr[dad], arr[son]);
    dad = son;
    son = dad * 2 + 1;
    }
    }
    }
    
    void heap_sort(int arr[], int len) {
    //初始化,i从最后一个父节点开始调整
    for (int i = len / 2 - 1; i >= 0; i--)
    max_heapify(arr, i, len - 1);
    //先将第一个元素和已经排好的元素前一位做交换,再从新调整(刚调整的元素之前的元素),直到排序完成
    for (int i = len - 1; i > 0; i--) {
    swap(arr[0], arr[i]);
    max_heapify(arr, 0, i - 1);
    }
    }
    
    int main() {
    int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    heap_sort(arr, len);
    for (int i = 0; i < len; i++)
    cout << arr[i] << ' ';
    cout << endl;
    return 0;
    }

    6 归并排序

    归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

    算法思想:1.把长度为n的输入序列分成两个长度为n/2的子序列;2. 对这两个子序列分别采用归并排序;3. 将两个排序好的子序列合并成一个最终的排序序列。

    11100724366639b8cf71766122ed2833.png


    代码:

    void print(int a[], int n){
      for(int j= 0; j<n; j++){
        cout<<a[j] <<"  ";
      }
      cout<<endl;
    }
    
    //将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]
    void Merge(ElemType *r,ElemType *rf, int i, int m, int n)
    {
      int j,k;
      for(j=m+1,k=i; i<=m && j <=n ; ++k){
        if(r[j] < r[i]) rf[k] = r[j++];
        else rf[k] = r[i++];
      }
      while(i <= m)  rf[k++] = r[i++];
      while(j <= n)  rf[k++] = r[j++];
      print(rf,n+1);
    }
    
    void MergeSort(ElemType *r, ElemType *rf, int lenght)
    {
      int len = 1;
      ElemType *q = r ;
      ElemType *tmp ;
      while(len < lenght) {
        int s = len;
        len = 2 * s ;
        int i = 0;
        while(i+ len <lenght){
          Merge(q, rf,  i, i+ s-1, i+ len-1 ); //对等长的两个子表合并
          i = i+ len;
        }
        if(i + s < lenght){
          Merge(q, rf,  i, i+ s -1, lenght -1); //对不等长的两个子表合并
        }
        tmp = q; q = rf; rf = tmp; //交换q,rf,以保证下一趟归并时,仍从q 归并到rf
      }
    }
    
    int main(){
      int a[10] = {2,3,4,5,15,19,26,27,36,38,44,46,47,48,50};
      int b[10];
      MergeSort(a, b, 15);
      print(b,15);
      cout<<"结果:";
      print(a,10);
    }

    7 希尔排序

    希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序.

    算法思想

    1. 选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;
    2. 按增量序列个数k,对序列进行k 趟排序;
    3. 每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

    8f68e5685ba8d5dca6ec66b2a2b7a12f.png


    代码:

    void shell_sort(T array[], int length) {
        int h = 1;
        while (h < length / 3) {
            h = 3 * h + 1;
        }
        while (h >= 1) {
            for (int i = h; i < length; i++) {
                for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {
                    std::swap(array[j], array[j - h]);
                }
            }
            h = h / 3;
        }
    }

    8 计数排序

    计数排序统计小于等于该元素值的元素的个数i,于是该元素就放在目标数组的索引i位(i≥0)。

    • 计数排序基于一个假设,待排序数列的所有数均为整数,且出现在(0,k)的区间之内。
    • 如果 k(待排数组的最大值) 过大则会引起较大的空间复杂度,一般是用来排序 0 到 100 之间的数字的最好的算法,但是它不适合按字母顺序排序人名。
    • 计数排序不是比较排序,排序的速度快于任何比较排序算法。

    算法思想

    1. 找出待排序的数组中最大和最小的元素;
    2. 统计数组中每个值为 i 的元素出现的次数,存入数组 C 的第 i 项;
    3. 对所有的计数累加(从 C 中的第一个元素开始,每一项和前一项相加);
    4. 向填充目标数组:将每个元素 i 放在新数组的第 C[i] 项,每放一个元素就将 C[i] 减去 1;

    af35101546bf5e60699380397c33f2a3.gif


    代码:

    #include <iostream>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    // 计数排序
    void CountSort(vector<int>& vecRaw, vector<int>& vecObj)
    {
    // 确保待排序容器非空
    if (vecRaw.size() == 0)
    return;
    
    // 使用 vecRaw 的最大值 + 1 作为计数容器 countVec 的大小
    int vecCountLength = (*max_element(begin(vecRaw), end(vecRaw))) + 1;
    vector<int> vecCount(vecCountLength, 0);
    
    // 统计每个键值出现的次数
    for (int i = 0; i < vecRaw.size(); i++)
    vecCount[vecRaw[i]]++;
    
    // 后面的键值出现的位置为前面所有键值出现的次数之和
    for (int i = 1; i < vecCountLength; i++)
    vecCount[i] += vecCount[i - 1];
    
    // 将键值放到目标位置
    for (int i = vecRaw.size(); i > 0; i--)// 此处逆序是为了保持相同键值的稳定性
    vecObj[--vecCount[vecRaw[i - 1]]] = vecRaw[i - 1];
    }
    
    int main()
    {
    vector<int> vecRaw = { 0,5,7,9,6,3,4,5,2,8,6,9,2,1 };
    vector<int> vecObj(vecRaw.size(), 0);
    
    CountSort(vecRaw, vecObj);
    
    for (int i = 0; i < vecObj.size(); ++i)
    cout << vecObj[i] << "  ";
    cout << endl;
    
    return 0;
    }

    9 桶排序

    将值为i的元素放入i号桶,最后依次把桶里的元素倒出来。

    算法思想

    1. 设置一个定量的数组当作空桶子。
    2. 寻访序列,并且把项目一个一个放到对应的桶子去。
    3. 对每个不是空的桶子进行排序。
    4. 从不是空的桶子里把项目再放回原来的序列中。

    be73e28e60e9096886e625793c0f5683.png


    代码:

    function bucketSort(arr, bucketSize) {
        if (arr.length === 0) {
          return arr;
        }
    
        var i;
        var minValue = arr[0];
        var maxValue = arr[0];
        for (i = 1; i < arr.length; i++) {
          if (arr[i] < minValue) {
              minValue = arr[i];                // 输入数据的最小值
          } else if (arr[i] > maxValue) {
              maxValue = arr[i];                // 输入数据的最大值
          }
        }
    
        // 桶的初始化
        var DEFAULT_BUCKET_SIZE = 5;            // 设置桶的默认数量为5
        bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
        var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
        var buckets = new Array(bucketCount);
        for (i = 0; i < buckets.length; i++) {
            buckets[i] = [];
        }
    
        // 利用映射函数将数据分配到各个桶中
        for (i = 0; i < arr.length; i++) {
            buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
        }
    
        arr.length = 0;
        for (i = 0; i < buckets.length; i++) {
            insertionSort(buckets[i]);                      // 对每个桶进行排序,这里使用了插入排序
            for (var j = 0; j < buckets[i].length; j++) {
                arr.push(buckets[i][j]);
            }
        }
    
        return arr;
    }

    10 基数排序

    一种多关键字的排序算法,可用桶排序实现。

    算法思想

    1. 取得数组中的最大数,并取得位数;
    2. arr为原始数组,从最低位开始取每个位组成radix数组;
    3. 对radix进行计数排序(利用计数排序适用于小范围数的特点)

    f7df53edccdce77f58ddad1fd4daefb5.gif


    代码:

    int maxbit(int data[], int n) //辅助函数,求数据的最大位数
    {
        int maxData = data[0];///< 最大数
        /// 先求出最大数,再求其位数,这样有原先依次每个数判断其位数,稍微优化点。
        for (int i = 1; i < n; ++i)
        {
            if (maxData < data[i])
                maxData = data[i];
        }
        int d = 1;
        int p = 10;
        while (maxData >= p)
        {
            //p *= 10; // Maybe overflow
            maxData /= 10;
            ++d;
        }
        return d;
    /*    int d = 1; //保存最大的位数
        int p = 10;
        for(int i = 0; i < n; ++i)
        {
            while(data[i] >= p)
            {
                p *= 10;
                ++d;
            }
        }
        return d;*/
    }
    void radixsort(int data[], int n) //基数排序
    {
        int d = maxbit(data, n);
        int *tmp = new int[n];
        int *count = new int[10]; //计数器
        int i, j, k;
        int radix = 1;
        for(i = 1; i <= d; i++) //进行d次排序
        {
            for(j = 0; j < 10; j++)
                count[j] = 0; //每次分配前清空计数器
            for(j = 0; j < n; j++)
            {
                k = (data[j] / radix) % 10; //统计每个桶中的记录数
                count[k]++;
            }
            for(j = 1; j < 10; j++)
                count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
            for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
            {
                k = (data[j] / radix) % 10;
                tmp[count[k] - 1] = data[j];
                count[k]--;
            }
            for(j = 0; j < n; j++) //将临时数组的内容复制到data中
                data[j] = tmp[j];
            radix = radix * 10;
        }
        delete []tmp;
        delete []count;
    }
    © 2020 GitHub, Inc
    正在跳转​jq.qq.com
    展开全文
  • Dijkstra算法 c语言实现

    2021-05-24 05:50:41
    Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。Dijkstra算法是很有代表性的最短路算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。其基本思想是...

    Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。

    Dijkstra算法是很有代表性的最短路算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。

    其基本思想是,设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。

    初始时,S中仅含有源。设u是G的某一个顶点,把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径,并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u,将u添加到S中,同时对数组dist作必要的修改。一旦S包含了所有V中顶点,dist就记录了从源到所有其它顶点之间的最短路径长度。

    例如,对下图中的有向图,应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下表中。

    c0146088e71c7f9b7343313de71dd6c9.png

    Dijkstra算法的迭代过程:

    1eb713074c1466666300f2172400d523.png

    #include

    #include

    #include

    #define X 10000

    #define VertexNum 7 //实际上共有六个顶点(1---6)

    #define EdgeNum 9

    int Graph[VertexNum][VertexNum] =

    //0 1 2 3 4 5 6

    { X, X, X, X, X, X, X, //0

    X, X, 6, 3, X, X, X, //1

    X, X, X, X, 5, X, X, //2

    X, X, 2, X, 3, 4, X, //3

    X, X, X, X, X, X, 3, //4

    X, X, X, X, 2, X, 5, //5

    X, X, X, X, X, X, X //6

    };

    int Visited[VertexNum];

    int path[VertexNum];

    int Distance[VertexNum];

    void Dijkstra(int Begin)

    {

    int MinEdge, Vertex, i,j, Edges;

    Edges = 1;

    Visited[Begin] = 1;

    for (i = 1; i

    Distance[Begin] = 0;

    printf(" 1 2 3 4 5 6\n");

    printf("-----------------------------------\n");

    printf("s:%d", Edges);

    for( i=1; i

    if (Distance[i] == X) printf(" *"); else printf("%3d",Distance[i]);

    printf("\n");

    while( Edges

    {

    Edges++; MinEdge = X;

    for(j=1; j

    if (Visited[j]==0 && MinEdge > Distance[j] )

    {

    Vertex = j; MinEdge = Distance[j];

    }

    Visited[Vertex] = 1;

    printf("s:%d",Edges);

    for(j=1; j

    {

    if (Visited[j] == 0 && Distance[Vertex] + Graph[Vertex][j]

    { Distance[j] = Distance[Vertex] + Graph[Vertex][j];

    path[j] = Vertex;

    }

    //printf("%6d",Distance[j]);

    if (Distance[j] == X) printf(" *"); else printf("%3d",Distance[j]);

    }

    printf("\n");

    }

    }

    void main()

    {

    int i;

    int k;

    // clrscr();

    for(i=0; i

    Dijkstra(1);

    printf("\n\nAll Path-------------------------\n");

    for(i=2; i

    {

    printf("[%d] ",Distance[i]);

    k = i;

    do

    {

    printf("%d

    k = path[k];

    } while (k!=1);

    printf("1 \n");

    }

    }

    以上代码参考了数据结构课本

    下面的是网上的代码:

    以下是具体的实现(C/C++):

    /***************************************

    * About: 有向图的Dijkstra算法实现

    * Author: Tanky Woo

    * Blog: www.WuTianQi.com

    ***************************************/

    #include

    using namespace std;

    const int maxnum = 100;

    const int maxint = 999999;

    void Dijkstra(int n, int v, int *dist, int *prev, int c[maxnum][maxnum])

    {

    bool s[maxnum]; // 判断是否已存入该点到S集合中

    for(int i=1; i<=n; ++i)

    {

    dist[i] = c[v][i];

    s[i] = 0; // 初始都未用过该点

    if(dist[i] == maxint)

    prev[i] = 0;

    else

    prev[i] = v;

    }

    dist[v] = 0;

    s[v] = 1;

    // 依次将未放入S集合的结点中,取dist[]最小值的结点,放入结合S中

    // 一旦S包含了所有V中顶点,dist就记录了从源点到所有其他顶点之间的最短路径长度

    for(int i=2; i<=n; ++i)

    {

    int tmp = maxint;

    int u = v;

    // 找出当前未使用的点j的dist[j]最小值

    for(int j=1; j<=n; ++j)

    if((!s[j]) && dist[j]

    {

    u = j; // u保存当前邻接点中距离最小的点的号码

    tmp = dist[j];

    }

    s[u] = 1; // 表示u点已存入S集合中

    // 更新dist

    for(int j=1; j<=n; ++j)

    if((!s[j]) && c[u][j]

    {

    int newdist = dist[u] + c[u][j];

    if(newdist < dist[j])

    {

    dist[j] = newdist;

    prev[j] = u;

    }

    }

    }

    }

    void searchPath(int *prev,int v, int u)

    {

    int que[maxnum];

    int tot = 1;

    que[tot] = u;

    tot++;

    int tmp = prev[u];

    while(tmp != v)

    {

    que[tot] = tmp;

    tot++;

    tmp = prev[tmp];

    }

    que[tot] = v;

    for(int i=tot; i>=1; --i)

    if(i != 1)

    cout << que[i] << " -> ";

    else

    cout << que[i] << endl;

    }

    int main()

    {

    freopen("input.txt", "r", stdin);

    // 各数组都从下标1开始

    int dist[maxnum]; // 表示当前点到源点的最短路径长度

    int prev[maxnum]; // 记录当前点的前一个结点

    int c[maxnum][maxnum]; // 记录图的两点间路径长度

    int n, line; // 图的结点数和路径数

    // 输入结点数

    cin >> n;

    // 输入路径数

    cin >> line;

    int p, q, len; // 输入p, q两点及其路径长度

    // 初始化c[][]为maxint

    for(int i=1; i<=n; ++i)

    for(int j=1; j<=n; ++j)

    c[i][j] = maxint;

    for(int i=1; i<=line; ++i)

    {

    cin >> p >> q >> len;

    if(len < c[p][q]) // 有重边

    {

    c[p][q] = len; // p指向q

    c[q][p] = len; // q指向p,这样表示无向图

    }

    }

    for(int i=1; i<=n; ++i)

    dist[i] = maxint;

    for(int i=1; i<=n; ++i)

    {

    for(int j=1; j<=n; ++j)

    printf("%8d", c[i][j]);

    printf("

    ");

    }

    Dijkstra(n, 1, dist, prev, c);

    // 最短路径长度

    cout << "源点到最后一个顶点的最短路径长度: " << dist[n] << endl;

    // 路径

    cout << "源点到最后一个顶点的路径为: ";

    searchPath(prev, 1, n);

    }

    输入数据:

    5

    7

    1 2 10

    1 4 30

    1 5 100

    2 3 50

    3 5 10

    4 3 20

    4 5 60

    输出数据:

    999999 10 999999 30 100

    10 999999 50 999999 999999

    999999 50 999999 20 10

    30 999999 20 999999 60

    100 999999 10 60 999999

    源点到最后一个顶点的最短路径长度: 60

    源点到最后一个顶点的路径为: 1 -> 4 -> 3 -> 5

    最后给出两道题目练手,都是直接套用模版就OK的:

    1.HDOJ 1874 畅通工程续

    http://www.wutianqi.com/?p=1894

    2.HDOJ 2544 最短路

    http://www.wutianqi.com/?p=1892

    展开全文
  • 最短路径——Dijkstra算法C语言实现)

    千次阅读 多人点赞 2020-11-21 12:04:55
    最短路径(Dijkstar算法) 基本概念: 1)最短路径:非带权图——边数最少的路径;...算法:Dijkstra算法 输入:有向网图 G=(V,E) 源点 v 输出:从 v 到其他“所有顶点”的最短路径 1. 初始化:集合S = {v};
  • 想写出精炼、优秀的代码,不通过不断的锤炼,是很难做到的。二、八大排序算法排序算法作为数据结构的重要部分,系统地学习一下是很有必要的。1、排序的概念排序是计算机内经常进行的一种操作,其目的是将一组“无序...
  • 写在前面:博主是一位普普通通的19届二本大学生,平时最大的爱好就是听听歌,逛逛B站。博主很喜欢的一句话花开堪折直须折,莫待无花空折枝:博主的理解是头一次为人,就应该做自己想...求最短路径的两种算法简介 2.迪.
  • Dijkstra算法用于求解单源点之间的最短路径,但是图中不能存在某条边的权为负数的回路。 Dijkstra就是指定某个源点u,之后去寻找到这个源点距离最短的边(u,v),并利用这条边对其他的边进行松弛的概念,之后不断...
  • 思想类似于Prim算法,使用贪心的策略,每次从lowcost数组中选择最小值归入最短路径,并且根据已经并入的节点更新lowcost数组,具体细节可见代码代码 使用临界矩阵存储为例,代码如下 #define MAX_VEXNUM 100 ...
  • Dijkstra算法C语言程序

    万次阅读 多人点赞 2017-02-04 23:21:53
    Dijikstra算法是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中...百度百科:Dijkstra算法。 维基百科:Dijkstra's Algorithm。 C语言程序(去除了原文中非标准的C语言代码): #include #define INFINIT
  • 最短路径之Dijkstra算法 C语言实现

    万次阅读 多人点赞 2017-03-14 21:04:50
    Dijkstra算法(单源点路径算法,要求:图中不存在负权值边): 步骤: a. 初始时,S只包含源点,即S={v},v的距离为0。U包含除v外的其他顶点,即: U={其余顶点},若v与U中顶点u有边,则u的距离设置为相应的...
  • 基于堆实现Dijkstra算法C语言实现。。。。。。。。。。。。。。。
  • C语言实现Dijkstra算法(邻接矩阵与邻接表存储方式) 代码 #include <stdio.h> #include <stdlib.h> typedef int ArcType; typedef char VerTextType[20]; #define MVNum 100 //顶点最大数 #define ...
  • #include<stdio.h> #include<stdlib.h> #include<math.h> int map[7][7]={ 0,2,4,1,pow(2,30)-1,pow(2,30)-1,pow(2,30)-1, 2,0,pow(2,30)-1,3,10,pow(2,30)-1,pow(2,30)-1, 4,pow(2,30)-1,0,2,pow...
  • C语言:迪杰斯特拉(Dijkstra)算法

    千次阅读 2020-07-17 20:48:18
    目录引言算法思想实现代码 引言 日常生活中,当我们出去旅游、办事等等,面对陌生的环境,我们常常需要规划自己的路线,来使移动的距离最短或是开销最低。那么,今天给大家简单介绍一种针对有向网图的最短路径算法...
  • Dijkstra算法与Floyd算法是计算最短路径的经典算法。其中Dijkstra算法计算一个结点到其他结点的最短路径,Floyd算法计算所有结点之间的最短路径。 Dijkstra算法 1959年由Dijkstra提出,算法采用标号法,有两种标号...
  • Dijkstra算法C语言详解

    万次阅读 多人点赞 2015-08-19 10:04:56
    迪杰斯特拉算法介绍迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个节点到其他节点的最短路径。 它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩展到终点为止。基本思想  通过...
  • Dijkstra算法C语言测试

    2020-12-03 17:26:01
    想研究Dijkstra算法,参考了这篇博客Dijkstra算法图文详解,但是这篇博文的代码部分写的不满意,所以自己写了个例子,记录一下。
  • 找出了以前的dijkstra代码,还是直接看代码爽 /*单源最短路:指定一个点到其余各个点的最短路径*/ /*dijkstra主要思想:通过边来松驰1号顶点到其余各个顶点的路程 复杂度N*2*/ /*每次找到离源点最近的一个顶点,...
  • Dijkstra算法 C语言实现

    2021-07-18 10:09:16
    示例图 输入流 ...从A点开始Dijkstra */ 代码 /* 功能模块:最短路径 适用领域:有向图 基础模块:Graph 辅助数组 */ #include<stdio.h> #include<stdlib.h> #define MAXSIZE 20 #defin
  • C语言 最短路径之Dijkstra算法 无向图

    千次阅读 2018-06-12 15:39:19
    Dijkstra算法简介 实现过程 代码实现 ...Dijkstra算法简介 ...Dijkstra算法和Prim算法非常相似(参照链接:C语言 Prim算法和Kruskal算法的实现和证明) 从上面可以看出,Dijkstra算法只是比...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,265
精华内容 2,106
关键字:

dijkstra算法c语言代码