Dijkstra C++模板

1 /******************************************************************************* 2 * Name: Dijkstra Function 3 * Description : Find the shortest path from the start point to all other points 4 * Parameter list: edge - adjacency matrix of the graph 5 *                 dist - array of the shortest distance from start point 6 *                 path - array of the shortest path 7 *                 order - the number of the vertex 8 *                 start - start point 9 *                 maxNum - max distance means there is no path10 ********************************************************************************/11  void dijkstra(int *edge, int *dist, int *path, const int order ,int start, const int maxNum)12 {13     bool *visited = new bool[order];14 15     memset(visited, 0, sizeof(bool) * order);    16     memset(dist, 0, sizeof(int) * order);17     for (int i = 0; i < order; i++)18     {19         path[i] = -1;20         dist[i] = maxNum;21     }22 23     visited[start] = true;24     dist[start] = 0;25 26     int curs = start;27     int minDist, tempDist, tempCurs;28 29     for (int i = 1; i < order; i++)30     {31         minDist = maxNum;32         for (int j = 0; j < order; j++)33         {34             if(!visited[j])35             {36                 tempDist = dist[curs] + *(edge + curs * order + j);37                 if ( tempDist < dist[j])38                 {39                     dist[j] = tempDist;40                     path[j] = curs;41                 }42                 if(minDist > dist[j])43                 {44                     minDist = dist[j];45                     tempCurs = j;46                 }47             }48         }49         curs = tempCurs;50         visited[curs] = true;51     }52     delete []visited;53 }

调用示例:

1     const int maxNum = 1e8;2     int a[5][5] = {{0, 10, maxNum, 30, 100},{maxNum, 0, 50, maxNum, maxNum},3     {maxNum, maxNum, 0, maxNum, 10}, {maxNum, maxNum, 20, 0, 60}, {maxNum, maxNum, maxNum, maxNum, 0}};4     int b[5];5     int d[5];6     dijkstra((int *)a, d, b, 5, 0, maxNum);

原文链接: https://www.cnblogs.com/ltang/archive/2010/11/02/1866863.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍