单源点最短路径

单源点最短路径的C实现

求解单源点最短路径的算法：

• 1构造所有节点间距离的矩阵（二维数组），无直接路径的为无穷
• 2构造到所有节点最短路径上前一结点数组nodeArray，初始全为源点
• 3构造源点到其他各结点的距离数组distanceArray，无直接路径的为无穷
• 4从数组distanceArray中选出距离最小的结点node,并入集合s（初始为空）
• 5遍历遍历每个不在s集合中的其他结点dot（distanceArray数组），若源点到node距离与node到dot的距离之和小于源点到dot距离，则更新distanceArray对应项的值，并同时更新nodeArray的值为node
• 6重复4-5直至无可选结点
• 7通过nodeArray从某结点出发不断寻找其前一结点，直至源点，此路径即为源点到该结点的最短路径

---

具体实现

#include <iostream>
#include <stdio.h>
#include <stdlib.h>


using namespace std;

/**
自定义比较大小，负数均视为无穷大，其他大小正常
x<y,return true
*/
bool lessThen(float x, float y);

/**
长度为len的s数组是否包含e
包含e，return true
*/
bool contain(int* s, int len, int e);

/**
得到到达e的最短路径字符串描述
keys[i]的值为起点到i的前一个结点索引
*/
string getPath(int *keys, int e);

/**
以size*size的二维数组paths为前提寻找最短路径，返回有效长度为len一维数组keys
keys[i]的值为起点到i的前一个结点索引
*/
int* findShortestPath(float **paths, int size, int& len);

int main()
{
    //节点数
    int size = 0;
    //读入节点数
    cout<<"请输入节点数：";
    cin>>size;
    cout<<endl;
    if(size <= 0)
    {
        cout<<"节点数非正数"<<endl;
        system("pause");
        return 0;
    }
    int i;
    int j;

    //路径集合size*size
    float** paths = new float*[size];

    for(i = 0; i < size; i++)
    {
        paths[i] = new float[size];
    }

    //读入路径集合
    //readPaths(paths);

    for(i = 0; i < size; i++)
    {
        for(j = 0; j < size; j++)
        {
            if(i == j)
                paths[i][j] = 0;
            else
            {
                cout<<"请输入节点"<<i<<"到节点"<<j<<"的距离(负数表示无穷大):";
                cin>>paths[i][j];
            }
        }
        cout<<endl;
    }

    //计算最短路径
    int len;
    int* keys = findShortestPath(paths, size, len);

    string path;
    for(i = 1; i < size; i++)
    {

        cout<<"到节点"<<i<<"的最短距离:";
        if(paths[0][i] > 0)
            cout<<paths[0][i];
        else
            cout<<"无穷大";
        cout<<endl;
        path = getPath(keys, i);
        cout<<"到节点"<<i<<"的最短路径:"<<path<<endl<<endl;;
    }

    //释放内存
    if(keys)
        delete keys;

    for(i = 0; i < size; i++)
    {
        if(paths[i])
            delete paths[i];
    }
    if(paths)
        delete paths;
    system("pause");
    return 0;
}

bool contain(int* s, int len, int e)
{
    while(len > 0)
    {
        if(*s == e)
            return true;
        s++;
        len--;
    }
    return false;
}

string getPath(int *keys, int e)
{
    string path;
    char* temp = new char[20];
    while(1)
    {

        sprintf(temp, "%d", e);
        path.append(temp);
        if(e == 0)
            break;
        e = keys[e];
        path.append(" <- ");
    }
    delete temp;
    return path;
}

int* findShortestPath(float **paths, int size, int& len)
{
    len = 0;
    int* keys = new int[size];


    int* shortest = new int[size];
    shortest[len] = 0;
    len++;

    int index = 0;

    int i;
    int min;
    int temp;

    for(i = 0; i < size; i++)
        keys[i] = 0;

    while(len < size - 1)
    {
        //遍历找到距离最短的节点
        min = -1;
        for(i = 1; i < size; i++)
        {
            if(!contain(shortest, len, i) && lessThen(paths[0][i], min))
            {
                min = paths[0][i];
                index = i;
            }
        }
        if(min < 0)
            break;
        //cout<<"find point:"<<index<<",path="<<min<<endl;
        shortest[len] = index;
        len++;

        //刷新各节点距离
        for(i = 1; i < size; i++)
        {
            if(i == index)
                continue;
            if(paths[index][i] > 0)
            {
                temp = min+paths[index][i];
                if(lessThen(temp, paths[0][i]))
                {
                    paths[0][i] = temp;
                    keys[i] = index;
                }
            }
            //cout<<"paths[0]["<<i<<"]="<<paths[0][i]<<endl;
        }
        cout<<endl;
    }
    delete shortest;
    return keys;
}

bool lessThen(float x, float y)
{
    if(x < 0)
        return false;
    if(y < 0)
        return true;
    return x < y;
}

运行效果

带权有向图：

最短路径结果：