设为首页 - 加入收藏 焦点技术网
热搜:java
当前位置:首页 >

最短路径Dijkstra算法实现

2016-04-05 21:50:11.0 java  
导读:本文Bovinitwo给大家介绍 最短路径Dijkstra算法实现。/* Dijkstra算方法(时间复杂度O(n^3)) 此程序实现由无向图找到源v0到其他节点的最短路径 */ #inc。。。
/*
Dijkstra算方法(时间复杂度O(n^3))
此程序实现由无向图找到源v0到其他节点的最短路径
*/
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
#define Member 9        
#define MAXINT 65535
typedef int shortpath_weight[Member];       //储存V0到各个节点的最短路径的权重和
typedef int shortpath_pre[Member];          //存储最短路径的前驱,如shortpath_pre[1]=5;就表示v0到v1的最短路径中,v1的前驱是v5
void shortest_Dijkstra(Mgraph G,int v0,shortpath_weight *D,shortpath_pre *P)
{
    int final[Member];//用final记录一个是否已找到v0到这个节点的最短路径
    int i=0,j=0,k=0;
//初始化
    for(i=0;i<G.Nodenum;++i)
    {
        final[i]=0;
        (*D)=G.matrix[v0][i];
        (*P)=0;
    }
    (*D)[v0]=0;
    final[v0]=1;
   
//主循环
 for(i=0;i<G.Nodenum-1;++i)
    {
        //找到下一个最短路径节点
        for(j=0;j<G.Nodenum;++j)
        {
            if(!final[j]&&(*D)[j]<min)
            {
                min=(*D)[j];
                k=j;
            }
        }
        final[k]=1;
        //由最新找到的节点,更新V0到未找到的最短路径节权值和,以及这些节点在V0到它们的最短路径的前驱
        for(j=0;j<G.Nodenum;++j)
        {
            if(!final[j]&&(min+G.matrix[k][j])<(*D)[j])
            {
                (*D)[j]=min+G.matrix[j];
                (*P)[j]=k;
            }
        }
    }
}

(编辑: Bovinitwo)

网友评论
相关文章