Dijkstra[狄克斯特拉] 算法 C语言实现

Dijkstra 求最短路径算法，从一堆点{0,1,2,3,4,5}里选择一点0，然后求从0到{1,2,3,4,5}的最短距离，因为只有一个起点，所以也称为单源最短路径算法。

下面是图示例：

步骤如下：

1.取距离起点最近的点且未处理过。若没有，则结束

2.分别逐个计算以该点为起点的所有点的距离+起点到该点的距离  是否小于 起点到该相邻点的距离， 若小于则更新该相邻到到起点的距离

3.将该点置为已处理状态

4.重复1.2.3

下面是C语言 利用数组简单实现

  1 #include 
  2 #include 
  3 #include 
  4 #if linux
  5 #include 
  6 #endif
  7 
  8 #define INT_MAX 0x80000000  // 代表无穷大
  9 #define POINT_NUM 6     //点数量
 10 #define SIDE_NUM 9      //边数量
 11 
 12 typedef struct __graph
 13 {
 14     unsigned v_to_other[POINT_NUM];    // 记录从0顶点到各个顶点间的最小权重
 15     unsigned sides[POINT_NUM][POINT_NUM];    // 边权重集合
 16     unsigned char processed[POINT_NUM];       // 处理过的顶点  处理过为1  否则为0
 17 }GRAPH, *PGRAPH;
 18 
 19 void InitGraph(PGRAPH pgraph)
 20 {
 21     // 初始化 0 到 各个顶点的最短距离
 22     for (size_t i = 0; i < POINT_NUM; i++)
 23     {
 24         pgraph->v_to_other[i] = INT_MAX;
 25     }
 26 
 27     // 已知 0->0 距离为0
 28     pgraph->v_to_other[0] = 0;
 29     pgraph->v_to_other[1] = 1;
 30     pgraph->v_to_other[2] = 2;
 31     pgraph->v_to_other[3] = 3;
 32     
 33     // 初始化各个边的距离
 34     for (size_t i = 0; i < POINT_NUM; i++)
 35     {
 36         for (size_t j = 0; j < POINT_NUM; j++)
 37         {
 38             if(i == j)
 39             {
 40                 pgraph->sides[i][j] = 0;
 41             } else {
 42                 pgraph->sides[i][j] = INT_MAX;
 43             }
 44         }
 45     }
 46     // 已知各个边的距离
 47     pgraph->sides[0][1] = 1;
 48     pgraph->sides[0][2] = 2;
 49     pgraph->sides[0][3] = 3;
 50     pgraph->sides[1][3] = 1;
 51     pgraph->sides[1][4] = 4;
 52     pgraph->sides[2][3] = 4;
 53     pgraph->sides[3][4] = 2;
 54     pgraph->sides[3][5] = 4;
 55     pgraph->sides[4][5] = 1;
 56 
 57     memset(pgraph->processed, 0, POINT_NUM);
 58     pgraph->processed[0] = 1;
 59 }
 60 
 61 // 获取距离起点最短的点的索引
 62 bool GetMinVToOther(PGRAPH pgraph, size_t *vindex)
 63 {
 64     unsigned min_v_to_other = INT_MAX;
 65     for (size_t i = 0; i < POINT_NUM; i++)
 66     {
 67         if(!pgraph->processed[i] && pgraph->v_to_other[i] < min_v_to_other)
 68         {
 69             min_v_to_other = pgraph->v_to_other[i];
 70             *vindex = i;
 71         }
 72     }
 73     return min_v_to_other != INT_MAX;
 74 }
 75 
 76 void Dijkstra(PGRAPH pgraph)
 77 {
 78     size_t vindex = 0;
 79     while (GetMinVToOther(pgraph, &vindex))
 80     {
 81         for (size_t i = 0; i < POINT_NUM; i++)
 82         {
 83             if(pgraph->sides[vindex][i] != INT_MAX)
 84             {
 85                  // 距离0的 j点最短距离 = i点最短距离 + i->j距离
 86                 unsigned distance = pgraph->v_to_other[vindex] + pgraph->sides[vindex][i];
 87                 // 如果从0->i->j的这条线段距离 比已知 0->j 的距离短的话，则更新0->j最短距离
 88                 if(distance < pgraph->v_to_other[i])
 89                 {
 90                     pgraph->v_to_other[i] = distance;
 91                 }
 92             }
 93         }
 94         pgraph->processed[vindex] = 1;
 95     }
 96     
 97 }
 98 
 99 int main(int argc, char *argv[])
100 {
101     GRAPH graph;
102     InitGraph(&graph);
103 
104     Dijkstra(&graph);
105 
106     for (size_t i = 0; i < POINT_NUM; i++)
107     {
108         printf("0->%lu : %u\n", i, graph.v_to_other[i]);
109     }
110     
111     return 0;
112 }