最短路径算法

页面分类: Photoshop路径

天下维客，你可以修改的网络知识库

单源最短路径有Dijkstra算法。

最短路径算法

利用 迪积斯特拉 算法求 " 有向图 " 中某点到其余各点的最短路径并输出从该点到各点的详细路径,以及总权值。这个程序一个是不可达点的输出不明显，最大的错误是重复释放了一个指针，增加了详细的注释，这或者会影响阅读代码，的确，过多的注释会让代码阅读者不能真正理解代码，当然这也要代码可读性高。是的代码应该强调，可读性，简洁性，其次才是高效性。

输入: 首先输入图的顶点数 n 边数 m 接着下一行输入源点 sourcePoint 然后输入每一条边的数据包括 起点s，终点e，权值v 包括起点，终点，权值 (顶点从 1 开始编号)

输出: 输出到各点的详细路径以及权值

事例: (建议用管道测试)

输入文件 data.txt 内容如下：

7 12

3

1 2 3

2 6 7

6 5 9

5 4 2

1 4 3

1 3 6

3 6 1

3 5 5

6 7 1

1 7 2

4 7 10

5 7 5

输出：

The shortest path as followed:

From 3 can't to 1!

From 3 can't to 2!

From 3 to 4: 3-5-4 total is: 7

From 3 to 5: 3-5 total is: 5

From 3 to 6: 3-6 total is: 1

From 3 to 7: 3-6-7 total is: 2

Press any key to continue

编译环境：VC ++ 6.0

Author ： 江南孤峰

Time ：2007--3--21

＃i nclude <stdio.h>

＃i nclude <process.h>

＃i nclude <stdlib.h>

＃i nclude <limits.h>

＃i nclude <malloc.h>

＃i nclude <string.h>

typedef struct Side{// 路径中的节点
 int point; // 节点编号
struct Side *next;
}DefSide;
typedef struct Result{// 最短路径属性
int flag; // 标记
int start;  // 路径的起始点，（除源点）
int totalVaule; // 整条路径的总权值 
DefSide *thead; // 路径经过的各个节点
}DefResult;
int main(){
int  sourcePoint;
int  nNode,nSide,s,e,v,i,j;
int  *meter,nflag;
DefResult *presult;
DefSide  *temp,*temp2;
scanf("%d %d",&nNode,&nSide);
scanf("%d",&sourcePoint);
// 用链表存储最短路径，共有(nNode-1)条路径,因为下标从1开始
presult = (DefResult *)malloc(sizeof(DefResult) * nNode);
// 分配对应大小的矩阵,为便于理解，行列下标都从1开始
meter=(int*)malloc(sizeof(int)*(nNode+1)*(nNode+1));
memset(meter,0,sizeof(int)*(nNode+1)*(nNode+1)); 
for(i = 1; i <= nSide; i ++){
 scanf("%d %d %d",&s,&e,&v); 
 *(meter + s * nNode + e) = v; 
}
   // 初始化从源点到各点的最短路径，并求出与源点直接连接权值最小的点
for(i = 1,v = INT_MAX; i <= nNode; i ++){
 // 标记从源点到对应点的最短路径未求出
 presult[i].flag = 0; 
 // 路径初始化为空
 presult[i].thead = NULL; 
 // 从源点到该点没有直接连接
 if(!*(meter + sourcePoint*nNode + i) ){
  // 路径没有起始点（除源点），设值为 -1
  presult[i].start = -1;
  // 路径长度初始化为最大: INT_MAX
  presult[i].totalVaule = INT_MAX;
  continue;
 }
 //  从源点到该点有直接连接，路径长度初始化为源点到该点的权值
 presult[i].totalVaule = *(meter + sourcePoint*nNode + i);
 //  路径从该点开始（除源点）
 presult[i].start = i;
 // 求出与源点直接连接权值最小的点，权值存于 v 中，点编号存于 s 中
 if(v > *(meter + sourcePoint*nNode + i)){
  v = *(meter + sourcePoint*nNode + i); 
  s = i; 
 }
}
// 标记该点不必考虑了，值为 0
*(meter + sourcePoint*nNode + s) = 0;
// 标记从源点到该点的最短路径已经找到
presult[s].flag = 1; 
//源点到源点也标记完成
presult[sourcePoint].flag = 1; 
// 从源点到 n 个顶点的最短路径是否求完，有两个点已经完成即
// 源点和与源点直接邻接并且权值最小的点，nflag 初始化为 2
for(nflag = 2; nflag <= nNode; nflag ++){
 // s是目前源点到其它点最短路径的结束点
 v = presult[s].totalVaule;
 // 扫描从 s  出发到其他各点的权值，以决定是否更新邻接表和路径链表
 for(i = 1; i <= nNode; i ++){
  if(*(meter + s*nNode + i) &&
   (v + *(meter + s*nNode + i) < presult[i].totalVaule)){
   presult[i].totalVaule = v + *(meter + s*nNode + i);
   presult[i].start = presult[s].start;
   // 更新从源点到点 i 的路径
   while(presult[i].thead){
    temp = presult[i].thead;
    presult[i].thead = temp -> next;
    free(temp);
   }
   if(presult[s].thead){
    temp2 = presult[i].thead = (DefSide*)malloc(sizeof(DefSide));
    presult[i].thead->point= presult[s].thead->point;
    temp = presult[s].thead;
    while(temp->next){
     temp = temp -> next;
     temp2 = temp2->next = (DefSide*)malloc(sizeof(DefSide));
     temp2->point = temp->point;
    }
    temp2 = temp2->next = (DefSide*)malloc(sizeof(DefSide));
    temp2->point = i;
    temp2->next = NULL;
   }
   else{
    presult[i].thead  = (DefSide*)malloc(sizeof(DefSide));
    presult[i].thead->point = i;
    presult[i].thead->next = NULL;
   }
  }
 }
 // 筛选目前结果中的最短路径
 for(j = 1,v = INT_MAX; j <= nNode; j ++){ 
  if(!presult[j].flag && presult[j].totalVaule 
       && presult[j].totalVaule < v){
   v = presult[j].totalVaule;
   s = j;
  }
 }
 // 标记从源点到 s 点的最短路径已经找到
 presult[s].flag = 1; 
 *(meter + sourcePoint*nNode + s) = 0; 
}
printf("The shortest path as followed:\n");
for(i = 1; i <= nNode; i ++){
 if(i == sourcePoint)
  continue;
 if(presult[i].start == -1){
  printf("From %d can't to %d!\n",sourcePoint,i);
  continue;
 }
 printf("From %d to %d: %d-%d",sourcePoint,i,sourcePoint,presult[i].start);
 temp = presult[i].thead;
 while(temp){
  printf("-%d",temp -> point);
  temp2 = temp;
  temp = temp -> next;
  free(temp2);
 }
 printf(" total is: %d\n",presult[i].totalVaule);
}
free(meter);
return EXIT_SUCCESS;
}

• 相关参见：路径
• 了解更多请进入文章查阅：路径；选区

参见

• Photoshop
• 选区

相关内容

• 图层
• 选区
• 通道

Template:Photoshop 路径导航