| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 4187 人关注过本帖
标题:求一个起点到一个终点的最短路径
只看楼主 加入收藏
caimuyin
Rank: 1
等 级:新手上路
威 望:1
帖 子:32
专家分:2
注 册:2015-3-23
结帖率:40%
收藏
已结贴  问题点数:20 回复次数:6 
求一个起点到一个终点的最短路径
图片附件: 游客没有浏览图片的权限,请 登录注册
图片附件: 游客没有浏览图片的权限,请 登录注册


[ 本帖最后由 caimuyin 于 2015-6-22 20:56 编辑 ]
搜索更多相关主题的帖子: 起点 
2015-06-22 14:26
caimuyin
Rank: 1
等 级:新手上路
威 望:1
帖 子:32
专家分:2
注 册:2015-3-23
收藏
得分:0 
求大神帮我解决下这个问题吧   我觉得 用个完全图 应该能解决吧、、
2015-06-22 14:26
caimuyin
Rank: 1
等 级:新手上路
威 望:1
帖 子:32
专家分:2
注 册:2015-3-23
收藏
得分:0 
第二张为地点的大致位置。。距离什么的  差点无所谓。
我觉得不用权也行吧。
2015-06-22 14:29
svip
Rank: 2
等 级:论坛游民
帖 子:1
专家分:10
注 册:2015-6-22
收藏
得分:10 
本人拒绝回答。因为俺是初学者。
2015-06-22 20:46
caimuyin
Rank: 1
等 级:新手上路
威 望:1
帖 子:32
专家分:2
注 册:2015-3-23
收藏
得分:0 
有没有高手在啊 。。比较急。。
2015-06-23 08:25
林月儿
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:湖南
等 级:版主
威 望:138
帖 子:2277
专家分:10647
注 册:2015-3-19
收藏
得分:10 
程序代码:
#include <stdio.h>

/*
vertex 顶点 source 源点
path length 路径长度
pioneer 前驱
adjacent matrix 邻接矩阵
*/
#define MaxSize 5

#define Infinity 1000

void Dijkstra(int vertex, int source, int PathLength[], int AdjacentMatrix[MaxSize][MaxSize],int pioneer[MaxSize])
{
    //标记顶点是否在集合S中,如果是,则值为1,否为0
    bool sign[vertex];
   
    for(int i=0; i<vertex; i++)
    {
        //初始化源点到其他各个顶点的最短路径长度
        PathLength[i]=AdjacentMatrix[source][i];
       
        sign[i]=false;
       
        //满足条件,说明顶点i与源点不相邻
        if(PathLength[i]==Infinity)
        {
            pioneer[i]=-1;
           
        }
        else
        {
            pioneer[i]=source;
        }
       
    }
   
    //初始化时,集合S中只有一个元素,源点
    PathLength[source]=0;
    sign[source]=true;
   
    for(int i=0; i<vertex; i++)
    {
        int temp=Infinity;
       
        int t=source;
       
       
           
       
        for(int j=0; j<vertex; j++)
        {
            if((!sign[j]) && (PathLength[j]<temp))
            {
                t=j;
                temp=PathLength[j];
            }
        }
       
        if(t==source) break;
       
        sign[t]=true;
    
       
        for(int j=0; j<vertex; j++)
        {
            if((!sign[j]) && (AdjacentMatrix[t][j]!=Infinity))
            {
                if(PathLength[j]>(PathLength[t]+AdjacentMatrix[t][j]))
                {
                   
                    PathLength[j]=PathLength[t]+AdjacentMatrix[t][j];
                    pioneer[j]=t;
                }
            }
        }
   
    }
   
   
}

void find(int pineer[MaxSize], int i, int AdjacentMatrix[MaxSize][MaxSize])
{
    while(pineer[i]!=-1)
    {
        //反向的
        printf("(%d, %d)%d ", pineer[i], i, AdjacentMatrix[pineer[i]][i]);
        i=pineer[i];
    }
}

int main(void)
{
    int AdjacentMatrix[MaxSize][MaxSize]={Infinity,8,32,Infinity,Infinity,
                            12,Infinity,16,15,Infinity,
                            Infinity,29,Infinity,Infinity,13,
                            Infinity,21,Infinity,Infinity,7,
                            Infinity,Infinity,27,19,Infinity
                            };
    int vertex=MaxSize;
   
    int source=3;
    
    int end=3; 
   
    int PathLength[MaxSize];
   
    int pioneer[MaxSize];//记录前顶点
   
    for(int i=0; i<MaxSize; i++)
    {
        //初始化前顶点为无穷大
        pioneer[i]=Infinity;
    }
   
    printf("请输入源点(0~4):");
   
    scanf("%d", &source);
    
    printf("请输入源点(0~4):");
   
    scanf("%d", &end);
    
    printf("\n最短路径和长度\n");
   
    Dijkstra(vertex, source, PathLength, AdjacentMatrix, pioneer);
   
    printf("\n源点%d到顶点%d : %d ", source, end, PathLength[end]);
    
    find(pioneer, end, AdjacentMatrix);
   
    return 0;
}

剑栈风樯各苦辛,别时冰雪到时春
2015-06-23 11:46
f4_8057
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2016-3-10
收藏
得分:0 
2016-03-26 11:25
快速回复:求一个起点到一个终点的最短路径
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.032400 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved