c++ - Dijkstra 算法运行缓慢

Question

我实现了 Dijkstra 算法，它确实有效。但是当我的图（很密集）有大约 500000 个顶点时，算法花费的时间太长（超过一分钟）。读取包含该图表的文件也需要异常长的时间。我不确定我的程序中的瓶颈是什么。下面是我的算法代码以及我用它制作的哈希表和堆实现。

Dijkstra 实施

#include "heap.cpp"
#include <list>
//#include <iostream>
#include <fstream>
//#include <string>
#include <iostream>
#include <sstream>
#include <chrono>
using namespace std::chrono;
using namespace std;

//Graph class
//representation of the graph
class Graph
{
public:
    //maps vertex ids to pointers to them
    hashTable* vertices;
    //used to get the unknown vertex with the smallest dv in O(log|V|) time
    //each node in the heap also stores a pointer to the vertex
    heap* unknown;
    //a list of the ids of the vectors
    list<string> nodes;
    Graph()
    {
        //simply creates the hashtable for vertices
        vertices = new hashTable();
    }

    class Vertex;

    //Edge Class
    //representation of the directed edge between two vertices
    //stores the weight of the edge and the vertex the edge points to
    class Edge
    {
    public:
        int weight;
        Vertex* destination;
        Edge(int cost, Vertex* to)
        {
            weight = cost;
            destination = to;
        }
    };

    //Vertex Class
    //stores the id, the shortest known distance from source vertex to it
    //the previous vector in that shortest known path
    //and a list of pointers to outgoing edges from it
    class Vertex
    {
    public:
        string id;
        int dv;
        Vertex* prev;
        list<Edge*> adjacent;
        Vertex(string name, int distance, Vertex* previous, list<Edge*> adjacentList)
        {
            id = name;
            dv = distance;
            previous = prev;
            adjacent = adjacentList;
        }
    };

//insert function
//returns false if the user is attempting to make a loop
//or if the weights entered either aren't positive or are greater than 1 million
//returns true on success
//inserts vertex id and pointer into the hashtable if not already there
//adds a pointer to the newly formed outgoing edge into v1's adjaency list

bool insert(string id1, string id2, int weight)
{
    if(id1.compare(id2) == 0 or weight < 0 or weight > 1000000)
    {
        return false;
    }

    //if the vertex hasn't been seen before
    if (not (vertices -> contains(id1)))
    {
        //create a pointer to the new vertex
        Vertex* vert1 = new Vertex(id1, INT_MAX,  nullptr, list<Edge *>());
        //insert it into the hashtable
        vertices -> insert(id1, vert1);
        //insert its id into nodes
        nodes.push_back(id1);
    }

    if (not (vertices -> contains(id2)))
    {
        Vertex * vert2 = new Vertex(id2, INT_MAX,  nullptr, list<Edge *>());
        vertices -> insert(id2, vert2);
        nodes.push_back(id2);
    }

    //update v1's adjaency list
    (((Vertex*)(vertices -> getPointer(id1))) -> adjacent).push_back(new Edge(weight, ((Vertex*)(vertices -> getPointer(id2)))));


    return true;
}


//finds shortest path from source vertex
//to every vertex in graph
//returns false if vertex given isn't in the graph
//true upon success
bool Dijkstra(Vertex source)
{
    if(not(vertices -> contains(source.id)))
    {
        return false;
    }

    //initialize the heap
    unknown = new heap(nodes.size());

    //insert every vertex id into the heap and set their keys to INT_MAX
    for (auto const& i: nodes)
    {
        unknown -> insert(i, INT_MAX, vertices ->getPointer(i));
    }

    //get the pointer for the source node from the hashtable
    Vertex * start = (Vertex *) vertices -> getPointer(source.id);
    //set its dv to 0
    start -> dv = 0;
    //fix the heap
    unknown -> setKey(source.id, 0);

    Vertex* chosen;
    int iterations = 0;
    string id;

    for(int iterations = 0; iterations < nodes.size(); iterations ++)
    {
        //extract from heap unknown vertex with smallest dv
        unknown -> deleteMin(nullptr, nullptr, &chosen);

        //if the min dv in this heap is INT_MAX
        //the rest of the unknown vertices don't have a path to the source vertex
        //so we're done and we can break
        if(chosen -> dv == INT_MAX)
        {
            //continue;
            break;
        }


        //go through its adjaency list and update values
        for (auto const& next : chosen -> adjacent)
        {
            //if chosen_dv + next -> weight < next_dv
            //update dv value on the destination vertex and in the heap
            //make prev of destination vertex chosen
            //else do nothing
            if(chosen -> dv + next -> weight < next -> destination -> dv)
            {
                next -> destination -> dv = chosen -> dv + next -> weight;
                next -> destination -> prev = chosen;
                unknown -> setKey(next -> destination -> id, next -> destination -> dv);
            }
        }
    }
    return true;
}

//gets shortest path from given vertex to source
string getPath(Vertex* source)
{
    //if we reached the source vertex
    if(source -> dv == 0)
    {
        //return its id
        return  source -> id + ", ";
    }
    //find the shortest path from the vertex before the given vertex in the path
    return  getPath(source -> prev) + source -> id + ", ";
}

//returns shortest path from source vertex to every vertex in graph
string printSolution()
{
    string output = "";
    Vertex* source;
    string path = "";

    //iterate through list of vertices
    for(auto const& start: nodes)
    {
        //get the pointer to the vertex from the hashtable
        source = (Vertex*)vertices -> getPointer(start);
        output += start + " : ";

        //if the dv is still INT_MAX, there was no path from the source to it
        if(source -> dv == INT_MAX)
        {
            path = "NO PATH\n";
        }
        else
        {
            output += to_string(source -> dv) + " ";
            path = "[" + getPath(source);
            path.erase(path.size() - 2);
            path += "]\n";
        }
        output += path;
    }
    return output.erase(output.size() - 1);
}



};

//prompts user for input
//processes and gives back the results
//of Dijkstra's Algorithm
void Processor()
{
    //variables that will store user input
    string input, output, vertex;

    //prompt user for graph file name
    cout << "Enter name of graph file: ";
    //store it in input
    cin >> input;

    //make graph object
    Graph* chart = new Graph();

    //open input file
    ifstream myfile;
    myfile.open(input);
    string line, arg;

    //vector of arguments to be fed into insert
    vector<string> arguments;
    while(getline(myfile, line))
    {
        stringstream ss(line);
        //parse each line by space to get arguments
        while(getline(ss, arg, ' ' ))
        {
            arguments.push_back(arg);
        }
        //insert into the graph
        chart -> insert(arguments[0], arguments[1], stoi(arguments[2]));
        arguments.clear();
    }
    myfile.close();

    while(true)
    {
        //prompt user for start vertex
        cout<< "Enter name of starting vertex: ";
        cin >>  vertex;
        //if the vertex isn't in the graph
        //keep on prompting them until they give a valid one
        if(chart -> vertices -> contains(vertex))
        {
            break;
        }
    }

    //get the start vertex from the hashtable
    Graph::Vertex source =  *(Graph::Vertex *)(chart -> vertices -> getPointer(vertex));

    //time Dijkstra's algorithm
    auto start = high_resolution_clock::now();
    chart -> Dijkstra(source);
    string result = chart -> printSolution();
    auto stop = high_resolution_clock::now();

    auto duration = duration_cast<milliseconds>(stop - start);

    cout << "Total time (in seconds) to apply Dijkstra's algorithm: "
         << float(duration.count())/1000<< endl;

    //prompt user for output file
    cout << "Enter name of output file: ";
    cin >> output;

    //open output file
    ofstream outfile;
    outfile.open(output);
    
    //write the results of the algorithm to the file
    outfile << result;
    outfile.close();

}

//just calls on Processor
int main()
{
    Processor();

    return 0;
}

堆

#include "heap.h"

//constructor for heap object
//capacity: measure of how much space in heap is left
//size: measure of how many elements (nodes) in heap
//map is a hashTable that allows for constant time access to pointers to nodes from their ids
//creates a hashTable
heap::heap(int length)
{
    data.resize(length + 1);
    capacity = length;
    size = 0;
    map = new hashTable(2*capacity);
}

//constructor for node object
//has an id which is used by the hashTable
//a key which is used to determine its position in the heap
heap::node::node(std::string identi, int pass, void* pvData)
{
    id = identi;
    key = pass;
    pData = pvData;
}

int heap::insert(const std::string &id, int key, void *pv)
{
    //if the heap is almost full, return 1
    if (size == capacity)
    {
        return 1;
    }
    //if the id is already in use, return 2
    if(map -> contains(id))
    {
        return 2;
    }
    int index = size + 1;
    node element(id, key, pv);
    data[index] = element;
    map -> insert(id, &data[index]);

    percolateUp(index);
    size += 1;
    return 0;
}

void heap::percolateDown(int posCur)
{
    int index = posCur;
    int child;
    node element = data[index];

    while(index*2 <= size)
    {
        child = index *2;
        if(child != size and data[child + 1].key < (data[child].key))
        {
            child += 1;
        }

        if(data[child].key < element.key)
        {
            data[index] = data[child];
            map -> setPointer(data[index].id, &data[index]);
            index = child;
        }
        else
        {
            break;
        }
    }
    data[index] = element;
    map -> setPointer(data[index].id, &data[index]);
}


void heap::percolateUp(int posCur)
{
    int index = posCur;
    node element = data[index];

    while(index > 1 and element.key < data[index /2].key)
    {
        data[index] = data[index / 2];
        map -> setPointer(data[index].id, &data[index]);
        index = index / 2;
    }
    data[index] = element;
    map -> setPointer(data[index].id, &data[index]);
}

int heap::setKey(const std::string &id, int key)
{
    if (not map -> contains(id))
    {
        return 1;
    }

    node *element = ((node*)(map -> getPointer(id)));
    int index = getPos(element);
    data[index].key = key;

    percolateUp(index);

    index = getPos(element);

    percolateDown(index);

    return 0;
}


int heap::remove(const std::string &id, int *pKey, void *ppData)
{
    if(size == 0 or not(map -> contains(id)))
    {
        return 1;
    }
    node * pv = ((node*)(map -> getPointer(id)));
    int index = getPos(pv);
    if(pKey != nullptr)
    {
        *pKey = data[index].key;
    }
    if(ppData != nullptr)
    {
        int *ppData = (int *)data[index].pData;
    }
    setKey(id, -INT_MAX);
    deletion(id);
    return 0;
}

int heap::deleteMin(std::string *pId, int *pKey, void *ppData)
{
    if(size == 0)
    {
        return 1;
    }
    if(pId != nullptr)
    {
        *pId = data[1].id;
    }
    if(pKey != nullptr)
    {
        *pKey = data[1].key;
    }
    if(ppData != nullptr)
    {
        *(static_cast<void **> (ppData)) = data[1].pData;
    }
    deletion(data[1].id);

    return 0;
}

void heap::deletion(std::string id)
{
    node * pv = ((node*)(map -> getPointer(id)));
    int index = getPos(pv);
    node removed = data[index];
    data[index] = data[size];

    data[size] = removed;
    map -> remove(data[size].id);
    size -= 1;
    percolateDown(index);
    percolateUp(index);

}

哈希表实现

#include "hash.h"
#include <typeinfo>

//returns a prime number depending on size required for hash table
//supports a size of up to one million
unsigned int hashTable::getPrime(int size)
{
    if (size <= 10000) { return 12373;}
    if (size <= 20000) {return 25867;}
    if (size <= 50000) {return 51479;}
    if (size <= 100000) {return 109211;}
    if (size <= 200000) {return 202717;}
    if (size <= 400000) {return 410299;}
    if (size <= 800000) {return 803549;}
    if (size <= 1600000) {return 2001101;}
    return 3200983;
}

// constructor for hashTable class
//takes initial size input and makes size of table from getPrime
//sets capacity to be initially the size of the hash table
hashTable::hashTable(int size)
{
    int num = getPrime(size);
    length = num;
    data.resize(num);
    capacity = length;
    filled = 0;
}



//hash function
//uses linear probing in the event of a collision
//which is where the function goes from the index
//where the initial hash sent the string to and 
//goes down the table until it either finds a free space
//or it finds the hashitem with that key value
int hashTable::hash(const std::string &key)
{
    int hashVal = 0;
    for(char ch: key)
    {
        hashVal = 37*hashVal + ch;
    }
    int i = 0;

    if (data[hashVal % length].isOccupied)
    {
        while( data[(hashVal + i) % length].isOccupied and 
            (data[(hashVal + i)% length].key).compare(key) != 0)
        {
            i += 1;
        }
    }
    return (hashVal + i) % length;
}

//insert function inserts key into position given by hash function
//changes filled and capacity number
//returns 0 on success, 1 when the key has already been inserted
//and 2 if there was a memory allocation error in the rehash function
//if the loading size exceeds 0.5, it rehashes
//this means that at any given time, the hashtable only uses a 1/3 of its actual size
//which is necessary in order to decrease the likelihood of collisions
int hashTable::insert(const std::string &key, void *pv)
{
    //if the key has already been inserted return 1
    //but if the hash item has been deleted, we could insert this key in its place
    //i didn't put this before, this could be what was missing from my code
    int index = hash(key);
    if (((data[index].key).compare(key) == 0) && not(data[index].isDeleted))
    {
        return 1;
    }
    data[index] = hashItem();
    data[index].isOccupied = true;
    data[index].isDeleted = false;
    data[index].key = key;
    data[index].pv = pv;
    filled += 1;
    capacity -= 1;
    if (filled/length > 0.7)
    {
        if (not rehash())
        {
            return 2;
        }
    }
    return 0;
}

//multiplies the size of the table by 2
//resizes it based on getPrime of new size
//uses a try catch block on the portion where
//the table is resized
//returns false if memory allocation error occurs
//true if successful
bool hashTable::rehash()
{
    int m = data.size();

    std::vector<hashItem> temp(data);
    //make temporary vector to contain key values
    //temp.resize(m);
    //temp = data;
    //get new size of hashtable
    int size = getPrime(m*2);
    //clear the contents of the hashtable
    data.clear();
    //try to double the size of the hashtable
    try
    {
        data.resize(size);
    }
    //catch any potential memory allocation error
    catch (std::bad_alloc)
    {
        return false;
    }
    //set capacity to size and filled to 0
    capacity = size;
    filled = 0;
    length = size;
    //insert the key into the resized and empty hashtable
    for(int i= 0; i < m; i++)
    {
        //only add in items that weren't deleted
        if(not temp[i].isDeleted && temp[i].isOccupied)
        {
            insert(temp[i].key);
            setPointer(temp[i].key, temp[i].pv);
            filled += 1;
            capacity -= 1;
        }
    }
    //deallocate memory from the temporary vector
    //std::vector<hashItem>().swap(temp);
    return true;
}

//checks if key is in hash table
bool hashTable::contains(const std::string &key)
{
    int index  = hash(key);
    return (data[index]).isOccupied and not((data[index]).isDeleted);
}


//sets pointer of hashItem associated with the key
//to input
int hashTable::setPointer(const std::string &key, void *pv)
{
    if(not contains(key))
    {
        return 1;
    }
    data[hash(key)].pv = pv;
    return 0;
}

//retrieves pointer in hashItem from hashtable
//also writes to a boolean pointer whether or not key is in the table
//returns nullptr if not in the table
void* hashTable::getPointer(const std::string &key, bool *b)
{
    bool con = contains(key);
    //bug
    b = &con;
    if(not con)
    {
        return nullptr;
    }
    return data[hash(key)].pv;
}



//removes an item from the hashtable
 //via lazy deletion
bool hashTable::remove(const std::string &key)
{
    if(not contains(key))
    {
        return false;
    }
    data[hash(key)].isDeleted = true;
    return true;
}

标签： c++algorithmruntimehashtabledijkstra