单源最短路径Dijkstra算法

Dijkstra算法中设置了一顶点集合S，从源点s到集合中的顶点的最终最短路径的权值均已确定。算法反复选择具有最短

路径估计的顶点u∈V - S，并将u加入S中，对u的所有出边进行松弛，在下列算法实现中，用到了顶点的最小优先队列

Q，排序关键字为顶点的d值。d为实时权值。

代码如下：

[cpp]
#include<iostream>
#include<list>
using namespace std;

#define MAXVALUE 10000          //定义一个最长路径

//此处Dijkstra算法的图为有向图

struct Edge
{
    int verno;          //邻接数组中节点编号
    int weight;         //权值
    Edge* next;         //指向下一条边
};

struct Vertex
{
    Edge *adj;          //所指向的节点所在边
    int verno;          //邻接数组中节点编号
    char key;           //关键字
};

struct Graph
{
    Vertex *vertexs;    //节点数组
    int vertexnum;      //节点个数
    int adjnum;         //边数
};

class MSWDijkstra
{
public:
    MSWDijkstra(char *vertex,int vernum,char adj[][2],int *weight,int adjnum);
    void DijkstraInsert(int source,int dest,int weight);
    int DijkstraFindKey(char key);
    int DijkstraExtraMin(bool *visited,int length);
    void DijkstraInitSingleSource();
    void DijkstraMSW(char sourceKey);
    void DijkstraOutput();
private:
    int *shortway;
    int *parent;
    Graph *dijkstraGraph;
};

MSWDijkstra::MSWDijkstra(char *vertex,int vernum,char adj[][2],int *weight,int adjnum)
{
    int i,source,dest;

    shortway = new int[vernum];
    parent = new int[vernum];
    dijkstraGraph = new Graph;

    dijkstraGraph->vertexs = new Vertex[vernum];
    dijkstraGraph->adjnum = adjnum;
    dijkstraGraph->vertexnum = vernum;
    for(i = 0;i < vernum;i++)
    {
        dijkstraGraph->vertexs[i].key = vertex[i];
        dijkstraGraph->vertexs[i].verno = i;
        dijkstraGraph->vertexs[i].adj = NULL;
    }

    for(i = 0;i < adjnum;i++)
    {
        source = DijkstraFindKey(adj[i][0]);
        dest = DijkstraFindKey(adj[i][1]);
        DijkstraInsert(source,dest,weight[i]);
        //DijkstraInsert(dest,source,weight[i]);            //无向图与有向图的区别在此
    }
}

void MSWDijkstra::DijkstraInsert(int source,int dest,int weight)
{
    if(dijkstraGraph->vertexs[source].adj == NULL || dijkstraGraph->vertexs[source].adj->weight > weight)
    {
        Edge* newnode = new Edge;
        newnode->verno = dest;
        newnode->weight = weight;
        newnode->next = dijkstraGraph->vertexs[source].adj;
        dijkstraGraph->vertexs[source].adj = newnode;
    }
    else
    {
        Edge* temp = dijkstraGraph->vertexs[source].adj;
        while(temp->next != NULL)                        //插入新边的时候，把权值从低到高进行排序
        {
            if(temp->next->weight > weight)
                break;
            temp = temp->next;
        }
        Edge* newnode = new Edge;
        newnode->verno = dest;
        newnode->weight = weight;
        newnode->next = temp->next;
        temp->next = newnode;
    }
}

int MSWDijkstra::DijkstraFindKey(char key)
{
    int i;
    for(i = 0;i < dijkstraGraph->vertexnum;i++)
    {
        if(dijkstraGraph->vertexs[i].key == key)
            break;
    }
    return i;
}

int MSWDijkstra::DijkstraExtraMin(bool *visited,int length)
{
    int min = MAXVALUE;
    for(int i = 0;i < length; i++)
    {
        if(!visited[i])
        {
            if(min != MAXVALUE && shortway[i] < shortway[min] || min == MAXVALUE)
                min = i;
        }
    }
    return min;
}

void MSWDijkstra::DijkstraInitSingleSource()
{
    int vernum = dijkstraGraph->vertexnum;
    for(int i = 0;i < vernum;i++)
    {
        shortway[i] = MAXV

补充：综合编程 , 其他综合 ,