Dijkstra算法求最短路径

2018-07-04T15:44:41

问题描述:带权图的存储结构的建立(邻接表、邻接矩阵);Dijkstra算法求最短路径。

实现要求:

(1)建立带权图的邻接矩阵或邻接表;

(2)实现Dijkstra算法求最短路径。

#include <cstdio>
#include <cstdlib>
const int maxv = 20;
//INF定义为无穷大,表示不连通
const int INF = 9999;

// MGraph类(邻接矩阵构建图类)
class MGraph
{
private:
    typedef struct
    {
        int edges[maxv][maxv];
        int n,e;
    }Graph;//定义图类型

    Graph *g;//定义图类型变量g

public:
    MGraph()//构造函数内,初始化成员g
    {
        g = (Graph*)malloc(sizeof(Graph));
    }
    // 构建图(邻接矩阵) 
    void create_MGraph()
    {
        printf("输入顶点数,边数(n e): ");
        scanf("%d%d",&g->n,&g->e);
        int i,j,w;
        //邻接矩阵的初始化9999
        for(int i = 0; i < g->n; i++)
        {
            for(int j = 0; j < g->n; j++)
            {
                g->edges[i][j] = INF;
            }
        }
        printf("输入边及权(i j weight):\n");
        for(int count = 0; count < g->e; count++)
        {
            scanf("%d%d%d",&i,&j,&w);
            g->edges[i][j] = w;
        }
    }
    // 打印图(邻接矩阵) 
    void print_MGraph()
    {
        for(int i = 0; i < g->n; i++)
        {
            for(int j = 0; j < g->n; j++)
            {
                printf(" %4d ",g->edges[i][j]);
            }
            printf("\n");
        }
    }
    // 输出任意顶点V0,到其他顶点的最短路径 
    void Dispath(int dist[],int path[],int S[],int v)
    {
        int k,d;
        //遍历输出
        for(int i = 0; i < g->n; i++)
            if(S[i] == 1 && i != v)
            {
                printf("V%d->V%d的最短路径长度为: %d\n",v,i,dist[i]);
                k = path[i];
                if(k == -1)
                    printf("无路径\n");
            }
    }
    // Dijkstra算法,求最短路径 
    void Dijkstra(int v)
    {
        int dist[maxv],path[maxv];
        int S[maxv];
        int mindist,u;
        //初始化
        for(int i = 0; i < g->n; i++)
        {
            //以v顶点开始到其他顶点的距离
            dist[i] = g->edges[v][i];
            S[i] = 0;
            if(g->edges[v][i] < INF)
                path[i] = v;
            else
                path[i] = -1;//无路径
        }
        //标记v已经是最短距离
        S[v] = 1,path[v] = 0;
        //Dijkstra算法开始
        for(int i = 0; i < g->n; i++)
        {
            mindist = INF;
            //求出当前dist数组中离v最短的距离的顶点的下标
            for(int j = 0; j < g->n; j++)
            {
                if(S[j] == 0 && dist[j] < mindist)
                {
                    //记下这个点的下标
                    u = j;
                    mindist = dist[j];
                }
            }
            S[u] = 1;
            //若找到其他途径比从v直接到目的顶点的距离短,则替换掉
            for(int j = 0; j < g->n; j++)
            {
                if(S[j] == 0)
                {
                    if(g->edges[u][j] < INF && dist[u] + g->edges[u][j] < dist[j])
                    {
                        dist[j] = dist[u] + g->edges[u][j];
                        path[j] = u;
                    }
                }
            }
        }
        Dispath(dist,path,S,v);
    }
    // g->n为MGraph类私有成员
    //只能通过函数访问,获得图的边数n
    int MGraph_n()
    {
        return g->n;
    }
};

int main()
{
    MGraph mgraph;//MGraph类,实例化对象mgarph
    //freopen("data.txt","r",stdin);
    printf("创建邻接矩阵\n");
    mgraph.create_MGraph();
    printf("---------------------\n");
    printf("打印邻接矩阵\n");
    mgraph.print_MGraph();
    printf("---------------------\n");
    //输出任意顶点V0,到其他顶点的最短路径 
    mgraph.Dijkstra(0);
    system("Pause");
    return 0;
}
/*
第一组:
4 4
0 1 9
1 2 8
0 2 7
3 2 6

第二组:
5 7
0 1 9
1 2 8
2 3 7
3 4 6
0 2 5
0 3 4
0 4 3
*/

 

当前页面是本站的「Baidu MIP」版。发表评论请点击:完整版 »
因本文不是用Markdown格式的编辑器书写的,转换的页面可能不符合MIP标准。