| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
Reworld,下班在家制作游戏,1500万奖金等你拿以码会友 以友辅仁
共有 912 人关注过本帖, 1 人收藏
标题:最短路径算法集锦
只看楼主 加入收藏
巧若拙
Rank: 4
来 自:宁波余姚
等 级:业余侠客
威 望:1
帖 子:159
专家分:273
注 册:2014-8-24
结帖率:46.15%
  问题点数:0  回复次数:1   
最短路径算法集锦
/*
    Name: 最短路径算法集锦
    Copyright:
    Author: 巧若拙
    Date: 12/11/14 15:32
    Description:
    列举了深度优先搜索的递归和非递归算法,Dijkstra最短路径算法,
    基于Bellman-Fort最短路径算法的改进型广度优先搜索算法,
    Floyd-Warshall最短路径算法的原始版和变化版
    本文是阅读《啊哈!算法》后的学习笔记,代码与教材中有些差异,若有错误请指正,谢谢!
    测试数据:
    5 7
    0 3 2
    0 4 9
    4 2 1
    4 1 3
    2 1 1
    3 4 2
    3 1 8
*/
#include<stdio.h>
#include<stdlib.h>

#define MAX 20   //最大顶点数量
#define MAXLEN 99999999   //最长路径

int book[MAX] = {0}; //标记该城市是否已经在路径中
int map[MAX][MAX] = {0};//邻接矩阵存储两城市间路程
int min = MAXLEN;  //城市间最短距离
int sum = 0;

int DeepSearchWay_1(int n, int startPos, int endPos);//深度优先搜索最短路径驱动程序
void dfs(int n, int curPos, int endPos, int dis);//深度优先搜索最短路径子程序
int DeepSearchWay_2(int n, int startPos, int endPos);//深度优先搜索最短路径非递归算法
int Dijkstra(int n, int startPos, int endPos);//Dijkstra最短路径算法
int bfs(int n, int startPos, int endPos);//改进的广度优先搜索最短路径算法
int Floyd(int n, int startPos, int endPos);//Floyd-Warshall最短路径算法
int Floyd2(int n, int startPos, int endPos);//Floyd-Warshall最短路径算法(原始版)
int Bellman(int n, int startPos, int endPos);//Bellman-Fort最短路径算法

int main()
{
    int i, j, m, n, a, b, c;
    int startPos, endPos;
   
    printf("请输入城市数量:");
    scanf("%d", &n);
    printf("\n请输入公路数量:");
    scanf("%d", &m);
   
    for (i=0; i<n; i++) //初始化顶点数据
    {
        for (j=0; j<n; j++)
        {
            map[i][j] = (i == j) ? 0 : MAXLEN;
        }
    }
    printf("\n请按照a b c格式输入城市间的道路信息:\n");
    for (i=0; i<m; i++)//读入城市间的道路信息
    {
        scanf("%d%d%d", &a,&b,&c);
        map[a][b] = c;
    }
   
    while (1)
    {
        printf("请输入起点城市编号:");
        scanf("%d", &startPos);
        printf("请输入终点城市编号:");
        scanf("%d", &endPos);
        
        min = DeepSearchWay_1(n, startPos, endPos);
        printf("深度优先搜索1: %d->%d = %d\n", startPos, endPos, min);
        
        min = DeepSearchWay_2(n, startPos, endPos);
        printf("深度优先搜索2:%d->%d = %d\n", startPos, endPos, min);
        
        min = Dijkstra(n, startPos, endPos);
        printf("Dijkstra最短路径算法:%d->%d = %d\n", startPos, endPos, min);  
        
        min = bfs(n, startPos, endPos);
        printf("改进的广度优先搜索:%d->%d = %d\n", startPos, endPos, min);  
        
        min = Floyd(n, startPos, endPos);
        printf("Floyd-Warshall最短路径算法:%d->%d = %d\n", startPos, endPos, min);  
        
        min = Floyd2(n, startPos, endPos);
        printf("Floyd-Warshall最短路径算法2:%d->%d = %d\n", startPos, endPos, min);  
        
        min = Bellman(n, startPos, endPos);
        printf("Bellman-Fort最短路径算法:%d->%d = %d\n", startPos, endPos, min);  
    }
   
   
   
    return 0;
}

int DeepSearchWay_1(int n, int startPos, int endPos)//深度优先搜索最短路径驱动程序
{
    int i;
   
    for (i=0; i<n; i++)
        book[i] = 0;
   
    sum = 0;   
    min = MAXLEN;  //城市间最短距离
    book[startPos] = 1;
    dfs(n, startPos, endPos, 0);
   
    printf("搜索次数为 %d\n", sum);
   
    return min;
}

void dfs(int n, int curPos, int endPos, int dis)//深度优先搜索最短路径子程序
{
    int i;
   
    if (dis > min) //当前路程已大于最短路程,直接返回
        return ;
   
    if (curPos == endPos)
    {
        if (dis < min)
            min = dis;
        return ;
    }
   
    for (i=0; i<n; i++)
    {
        if (book[i] == 0 && map[curPos][i] != MAXLEN)
        {
            book[i] = 1;
            dfs(n, i, endPos, dis+map[curPos][i]);
            book[i] = 0;
        }
        sum++;
    }
}

int DeepSearchWay_2(int n, int startPos, int endPos)//深度优先搜索最短路径非递归算法
{
    int Vex[MAX] = {0};
    int Stack[MAX] = {0};
    int Dis[MAX] = {0};
    int i, cur, top = 0;
    int sum = 0;
   
    for (i=0; i<n; i++)
        book[i] = 0;
   
    for (i=0; i<n; i++)
        Dis[i] = map[startPos][i];
        
    Stack[top] = startPos;
    book[startPos] = 1;
   
    while (top >= 0)
    {
        if (Vex[top] < n)
        {
            i = Vex[top];
            cur = Stack[top];
            if (book[i] == 0 && map[cur][i] != MAXLEN)
            {
                if (Dis[i] > Dis[cur] + map[cur][i]) //对各条边进行松弛
                {
                    Dis[i] = Dis[cur] + map[cur][i];
                }
               
                if (i != endPos)
                {
                    Stack[++top] = i;
                    book[i] = 1; //接入路径
                    Vex[top] = 0;
                }
                else
                    Vex[top]++;
            }
            else
            {
                Vex[top]++;
            }
            sum++;
        }
        else //退栈
        {
            book[Stack[top]] = 0; //离开路径
            top--;
            if (top >= 0) //转向下一条边
            {
                Vex[top]++;
            }
        }
    }
   
    printf("搜索次数为 %d\n", sum);
    return Dis[endPos];
}

int Dijkstra(int n, int startPos, int endPos)//Dijkstra最短路径算法
{
    int i, j, v, min;
    int Dis[MAX] = {0};
    int sum = 0;
   
    for (i=0; i<n; i++)
        book[i] = 0;
        
    for (i=0; i<n; i++)
        Dis[i] = map[startPos][i];
   
    book[startPos] = 1;   
    for (j=1; j<n; j++)
    {
        min = MAXLEN;  //城市间最短距离
        v = startPos;   
        for (i=0; i<n; i++) //寻找距离startPos最近的城市
        {
            if (book[i] == 0 && Dis[i] < min)
            {
                min = Dis[i];
                v = i;
            }
            sum++;
        }
        if (v == endPos) //已经找到最短路径
            break;   
        book[v] = 1;
        
        for (i=0; i<n; i++) //对城市v的边进行松弛
        {
            if (map[v][i] != MAXLEN)
            {
                if (Dis[i] > Dis[v] + map[v][i])
                    Dis[i] = Dis[v] + map[v][i];   
            }
            sum++;
        }
    }
   
    printf("搜索次数为 %d\n", sum);
    return Dis[endPos];
}

int bfs(int n, int startPos, int endPos)//改进的广度优先搜索最短路径算法
{
    int i, k, front, rear;
    int Dis[MAX] = {0};
    int Queue[MAX] = {0};
    int sum = 0;
   
    for (i=0; i<n; i++)
        book[i] = 0;
        
    for (i=0; i<n; i++)
        Dis[i] = MAXLEN;
        
    Dis[startPos] = 0;
    book[startPos] = 1;   
    front = rear = 0;
    Queue[rear++] = startPos;
    while (front != rear)
    {
        k = Queue[front];
        for (i=0; i<n; i++) //遍历结点k的各条边
        {
            if (Dis[i] > Dis[k] + map[k][i])
            {
                Dis[i] = Dis[k] + map[k][i];
            
                if (book[i] == 0)//入队列
                {
                    Queue[rear] = i;
                    rear = (rear + 1) % MAX;
                    book[i] = 1;
                }
            }
            sum++;
        }

        book[k] = 0;
        front = (front + 1) % MAX;
    }
   
    printf("搜索次数为 %d\n", sum);
    return Dis[endPos];
}

int Floyd(int n, int startPos, int endPos)//Floyd-Warshall最短路径算法
{
    int i, j, flag;
    int Dis[MAX] = {0};
    int sum = 0;
        
    for (i=0; i<n; i++)
        Dis[i] = map[startPos][i];

    flag = 1;
    while (flag)
    {
        flag = 0;
        for (i=0; i<n; i++)
        {
            for (j=0; j<n; j++)
            {
                if (Dis[i] > Dis[j] + map[j][i])
                {
                    Dis[i] = Dis[j] + map[j][i];
                    flag = 1;
                }
                sum++;
            }
        }
    }
   
    printf("搜索次数为 %d\n", sum);
    return Dis[endPos];
}

int Floyd2(int n, int startPos, int endPos)//Floyd-Warshall最短路径算法(原始版)
{
    int i, j, k;
    int Dis[MAX][MAX] = {0};
    int sum = 0;
        
    for (i=0; i<n; i++)
        for (j=0; j<n; j++)
            Dis[i][j] = map[i][j];

    for (k=0; k <n; k++)
    {
        for (i=0; i<n; i++)
        {
            for (j=0; j<n; j++)
            {
                if (Dis[i][j] > Dis[i][k] + Dis[k][j])
                {
                    Dis[i][j] = Dis[i][k] + Dis[k][j];
                }
                sum++;
            }
        }
    }
   
    printf("搜索次数为 %d\n", sum);
    return Dis[startPos][endPos];
}

int Bellman(int n, int startPos, int endPos)//Bellman-Fort最短路径算法
{
    int i, j, m = 0;
    int Dis[MAX] = {0};
    int u[MAX*MAX] = {0};
    int v[MAX*MAX] = {0};
    int w[MAX*MAX] = {0};
    int sum = 0;
        
    for (i=0; i<n; i++)
    {
        for (j=0; j<n; j++)
        {
            if (i != j && map[i][j] != MAXLEN)
            {
                u[m] = i;
                v[m] = j;
                w[m++] = map[i][j];
            }
        }
    }
        
    for (i=0; i<n; i++)
        Dis[i] = map[startPos][i];
        
    for (i=1; i<n; i++) //只需调整n-1次
    {
        for (j=0; j<m; j++)
        {
            if (Dis[v[j]] > Dis[u[j]] + w[j])
            {
                Dis[v[j]] = Dis[u[j]] + w[j];
            }
            sum++;
        }
    }
   
    printf("搜索次数为 %d\n", sum);
    return Dis[endPos];
}
搜索更多相关主题的帖子: Copyright include 
2014-11-13 22:28
seeksun
Rank: 1
等 级:新手上路
帖 子:5
专家分:5
注 册:2014-11-26
  得分:0 
正好需要,学习了。
2014-11-26 05:39
快速回复:最短路径算法集锦
数据加载中...
 
   





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

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