Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1546200
  • 博文数量: 124
  • 博客积分: 4078
  • 博客等级: 中校
  • 技术积分: 3942
  • 用 户 组: 普通用户
  • 注册时间: 2010-07-21 11:28
个人简介

新博客:http://sparkandshine.net/

文章分类

全部博文(124)

分类: C/C++

2011-06-29 21:17:48

这个很早就写了,先把源代码发上来了,其他内容择日补充。

一、最短路径算法


例子:


二、源代码

  1. /******************************
  2.  * date:2011-3-31
  3.  * filename:dijkstra_main.c
  4.  * by:Jelline
  5.  * ****************************/

  6. #include <stdio.h>

  7. #define MAX_WEIGHT 0X7FFFFFFF


  8. int dijkstra(int n, int adjMatrix[][n], int startV, int endV, int prev[]);

  9. void printShortestPath(int n, int adjMatrix[][n], int startV, int endV, const char **vertexStr);

  10. int main()
  11. {
  12.     //char vertex[] = {'a', '1', '2', '3', '4', '5', '6', 'b'};
  13.     const char *vertexStr[8] = {"a", "v1", "v2", "v3", "v4", "v5", "v6", "b"};
  14.     int adjMatrix[8][8] = {
  15.         {MAX_WEIGHT, 2, 8, 1, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT},
  16.         {2, MAX_WEIGHT, 6, MAX_WEIGHT, 1, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT},
  17.         {8, 6, MAX_WEIGHT, 7, 4, 2, 2, MAX_WEIGHT},
  18.         {1, 7, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 9, MAX_WEIGHT},
  19.         {MAX_WEIGHT, 1, 4, MAX_WEIGHT, MAX_WEIGHT, 3, MAX_WEIGHT, 9},
  20.         {MAX_WEIGHT, 2, MAX_WEIGHT, MAX_WEIGHT, 3, MAX_WEIGHT, 4, 6},
  21.         {MAX_WEIGHT, MAX_WEIGHT, 2, 9, MAX_WEIGHT, 4, MAX_WEIGHT, 2},
  22.         {MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 9, 6, 2, MAX_WEIGHT}
  23.     };
  24.     /*
  25.     int adjMatrix[8][8] = {
  26.       //{0, 1, 2, 3, 4, 5, 6, 7}
  27.         {0, 2, 8, 1, 0, 0, 0, 0},
  28.         {2, 0, 6, 0, 1, 0, 0, 0},
  29.         {8, 6, 0, 7, 4, 2, 2, 0},
  30.         {1, 7, 0, 0, 0, 0, 9, 0},
  31.         {0, 1, 4, 0, 0, 3, 0, 9},
  32.         {0, 2, 0, 0, 3, 0, 4, 6},
  33.         {0, 0, 2, 9, 0, 4, 0, 2},
  34.         {0, 0, 0, 0, 9, 6, 2, 0}
  35.     };
  36.     */

  37.     /*
  38.     int prev[8];
  39.     int shortestPath = dijkstra(8, adjMatrix, 0, 7, prev);
  40.     printf("the sum of shortest weight is %d\n", shortestPath);
  41.     */
  42.     printShortestPath(8, adjMatrix, 0, 7, vertexStr);

  43.     return 0;
  44. }


  45. /******************************************************
  46.  *Fuction:
  47.  * 求图最短路径长度,并存储迹
  48.  * Input:
  49.  * n--顶点个数
  50.  * adjMatrix[n][n]--图的邻接矩阵
  51.  * startV--源点
  52.  * endV--结束点
  53.  * prev[i]记录从源到顶点的最短路径上i的前一个顶点
  54.  *Out:
  55.  * 输出最短路径长度
  56.  * ******************************************************/

  57. int dijkstra(int n, int adjMatrix[][n], int startV, int endV, int prev[n])
  58. {
  59.     int dist[n]; //dist[i]表示从源到顶点i的最短特殊路径长度
  60.     int mask[n]; //mask[i]标记顶点i是否加入集合 -1表示已加入集合
  61.     int shortestPath = 0;
  62.     int minWeight = MAX_WEIGHT;
  63.     int minID;
  64.     int i;
  65.     int j;
  66.     int tmp = 0;

  67.     for (i=0; i<n; i++)
  68.     {
  69.         mask[i] = 0; //初始化集合为空集,即没有元素加入
  70.         dist[i] = adjMatrix[startV][i]; //初始化dist[j]
  71.         prev[i] = -1;
  72.         prev[i] = (adjMatrix[startV][i] != MAX_WEIGHT) ? startV : -1;
  73.     }


  74.     //prev[0] = startV;
  75.     // dist[startV] = -1; //起点标记为-1 不被更新
  76.     mask[startV] = -1; //标记源点已加入

  77.    for (i=1; i<n; i++) //最多再加入n-1个顶点
  78.    {
  79.        minWeight = MAX_WEIGHT;
  80.        //寻找下一个待加入的顶点
  81.        for (j=0; j<n; j++)
  82.        {
  83.            if (mask[j]!=-1 && dist[j]<minWeight)
  84.            {
  85.                minWeight = dist[j];
  86.                minID = j;
  87.            }
  88.        }
  89.        
  90.        mask[minID] = -1; //加入顶点

  91.        if (minID == endV) //最后一个节点已加入
  92.        {
  93.            return dist[endV];
  94.        }

  95.        //更新dist[i]
  96.        for (j=0; j<n; j++)
  97.        {
  98.            if (minWeight==MAX_WEIGHT || adjMatrix[minID][j]==MAX_WEIGHT)
  99.                continue;
  100.            tmp = minWeight + adjMatrix[minID][j];
  101.            if(j!=startV && tmp<dist[j]) //起点无须更新
  102.            {
  103.                dist[j] = tmp;
  104.                prev[j] = minID;
  105.            }
  106.        }

  107.    }
  108.     
  109. }

  110. //print path
  111. void printShortestPath(int n, int adjMatrix[][n], int startV, int endV, const char **vertexStr)
  112. {
  113.     int prev[n];
  114.     int shortestPath = dijkstra(n, adjMatrix, startV, endV, prev);
  115.     printf("the shortest path is: %d= ", shortestPath);
  116.    int tmp = endV;
  117.    do
  118.    {
  119.        printf("%s <--- ", vertexStr[tmp]);
  120.        tmp = prev[tmp];
  121.    }while(tmp != startV);
  122.    printf("%s\n", vertexStr[startV]);

  123. }


三、测试结果

  1. the shortest path is: 11= b <--- v6 <--- v2 <--- v4 <--- v1 <--- a
阅读(3283) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~