Shortest path algorithm in 0-1-unoriented graph

Question

I have an unoriented graph with n vertices and m edges, 1 <= n, m <= 100000. All edges have 0 or 1 weights (two vertices are connected even if the corresponding edge has 0 weight). Vertices indexing starts with 1. I need to find length of the shortest path from vertex A to vertex B.

Input data example:

4 5 1 3
1 2 1
2 3 0
3 4 1
4 1 1
1 3 0

From the first line I get: n = 4, m = 5, A = 1, B = 3. Then I get the elements of the adjacency list. The first number in each line is from-vertex, the second - to-vertex, and the last is the weight of current edge. 0 or 1.

In the output I must receive the length of the shortest path or -1 if the path doesn't exist.

Here is my solution using Dijkstra's algorithm:

#include <iostream>
...
using std::cout;
using std::cin;
using std::endl;
using std::vector;
using std::pair;
using std::string;
using std::map;
size_t INF = 200000;
int main() {
 size_t nVert,
 mEdges,
 start,
 end;
 cin >> nVert >> mEdges >> start >> end;
 vector<vector<pair<size_t, size_t>>> ajList(mEdges);
 size_t edStart, edEnd, weight;
 for (size_t vert = 0; vert < mEdges; ++vert) {
 cin >> edStart >> edEnd >> weight;
 ajList.at(edStart - 1).push_back(pair<size_t, size_t>(edEnd, weight));
 }
 vector<size_t> minLen(nVert, INF), 
 pred(nVert);
 minLen[start - 1] = 0;
 vector<char> used(nVert);
 for (size_t vert = 0; vert < nVert; ++vert) {
 size_t currentVert = -1;
 for (size_t j = 0; j < nVert; ++j) {
 if (!used[j] && (currentVert == -1 || minLen[j] < minLen[currentVert]))
 currentVert = j;
 }
 if (minLen[currentVert] == INF)
 break;
 used[currentVert] = true;
 for (size_t j = 0; j < ajList[currentVert].size(); ++j) {
 int to = ajList[currentVert][j].first - 1,
 len = ajList[currentVert][j].second;
 if (minLen[currentVert] + len < minLen[to]) {
 minLen[to] = minLen[currentVert] + len;
 pred[to] = currentVert;
 }
 }
 }
 if (minLen[end - 1] == INF)
 cout << -1;
 else
 cout << minLen[end - 1];
 return 0;
}

I know that Dijkstra is the fastest algorithm for searching the shortest path from one vertex to all other vertices, but in my case it takes too long.

• How can I optimize this code to make it working faster (this is the main problem)?
• If you see some bugs in this snippet, please, let me know.

• coderodde: Please consider splitting the code into meaningful subroutines. Don't let your main simulate the entire universe.

Answer 1

You should extract reading the data and the Dijkstra to their own method. It helps debugging. You don't have enough information to make a meaningful heuristic for A* anyway.

When filling the adjacency matrix you do it as if it is directional while your post says it's not:

for (size_t vert = 0; vert < mEdges; ++vert) {
 cin >> edStart >> edEnd >> weight;
 ajList.at(edStart - 1).push_back(pair<size_t, size_t>(edEnd, weight));
 ajList.at(edEnd - 1).push_back(pair<size_t, size_t>(edStart, weight));
}

I suggest you use a priority queue of some sort; it lets you remove the current node in \$O(\log n)\$ instead of \$O(n)\$ (the first inner for loop in your code).

Answer 2

How long is too long? How many vertices and edges does your sample test have? Did you measure the performance? How?

Also, in the initial phase of loading the edges in the ajList vector, for every edge from v -> w, you save them as (v - 1) -> w, not (v - 1) -> (w - 1). In others words, you changed the start vertex to a zero index system, but you didn't apply the same rule for the end vertex. You should apply the same rule for every vertex, i.e., manage all vertices in a X index way (being consistent is the key).

I recommend you to transform all vertices to a \0ドル\$ to \$N-1\$ range at the initial phase. Don't forget to apply this to the start and end vertices (given in the first line).