最短路径 dijsktra 模板

最短路径 dijsktra 模板

 

#include
using namespace std;

const int maxint = 9999999;
const int maxn = 1010;

int data[maxn][maxn], lowcost[maxn]; //data存放点点之间的距离，lowcost存放点到start的距离,从0开始存放
bool used[maxn];//标记点是否被选中
int n; //顶点的个数

void dijkstra(int start)//初始点是start的dij算法
{
    int i,j;
    
    memset(used, 0, sizeof(used));
    
    //inite
    for(i = 0; i < n; i++)
        lowcost[i] = data[start][i];
    
    used[start] = true;
    lowcost[start] = 0;
    
    for(i = 0; i < n-1; i++)
    {
        //choose min
        int tempmin = maxint;
        int choose;
        for(j = 0; j < n; j++)
        {
            if(!used[j] && tempmin > lowcost[j])
            {
                choose = j;
                tempmin = lowcost[j];
            }
        }
        used[choose] = true;
        
        //updata others
        for(j = 0; j < n; j++)
        {
            if(!used[j] && data[choose][j] < maxint && lowcost[choose]+data[choose][j] < lowcost[j])
                lowcost[j] = lowcost[choose]+data[choose][j];
        }
    }
}

int main()
{
    int start , i , j;
    cin>>n;
    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++)//输入顶点信息
        {      
            cin>>data[i][j];
        }
        cin>>start;
        dijkstra(start);
        int min = 0;
        for(i = 0; i < n; i++)
        {
            cout<< lowcost[i]<<" "; //输出各结点间的最小路径长度
            if(min < lowcost[i])
                min = lowcost[i];
        }
        cout<        cout<        return 0;
}
/*
3
0 1 2
3 0 4
5 6 0
1
输出：
3 0 4
4

*/

m为边数，n为定点数 ，时间复杂度O(n*n)

可以用二叉堆（优先队列）优化，时间复杂度O((m+n)log(n))

或者斐波那契堆优化，时间复杂度O(m+nlog(n))