lundi 6 mai 2019

Distance in Map Reaches Infinity When Origin Node is Greater Than Destination Node, but Not Vise-Versa

I've created a map that takes integers, when I try to set the origin node higher than the destination and the two aren't directly linked, it prints infinity.

For ex: Origin airport code #: 7 Destination airport code #: 0

I created a for loop that prints out distance to all vertices from the source, and if if I set the origin airport code to 7, and the destination to 3, it DOES print out the actual distance from 7 to 0.

How can I print the number that shows up in the for loop instead of infinity?

// Program to find Dijkstra's shortest path using 
// priority_queue in STL 

#include <vector>
// #include <bits/stdc++.h> 
// #include <stdc++.h> 
#include <queue> 
#include <iostream>

using namespace std; 

# define INF 0x3f3f3f3f 

// iPair ==> Integer Pair 
typedef pair<int, int> iPair; 

// To add an edge 
void addEdge(vector <pair<int, int> > adj[], int u, int v, int wt) { 
    adj[u].push_back(make_pair(v, wt)); 
    adj[v].push_back(make_pair(u, wt)); 
} 

// Prints shortest paths from src to all other vertices 
void shortestPath(vector <iPair> adj[], int V, int src) { 
    // Create a priority queue to store vertices that 
    // are being preprocessed. This is weird syntax in C++. 
    // Refer below link for details of this syntax 
    // http://geeksquiz.com/implement-min-heap-using-stl/ 
    priority_queue< iPair, vector <iPair>, greater<iPair> > pq; 

    // Create a vector for distances and initialize all 
    // distances as infinite (INF) 
    vector<int> dist(V, INF); 

    // Insert source itself in priority queue and initialize 
    // its distance as 0. 
    pq.push(make_pair(0, src)); 
    dist[src] = 0; 

    /* Looping till priority queue becomes empty (or all 
    distances are not finalized) */
    while (!pq.empty()) { 
        // The first vertex in pair is the minimum distance 
        // vertex, extract it from priority queue. 
        // vertex label is stored in second of pair (it 
        // has to be done this way to keep the vertices 
        // sorted distance (distance must be first item 
        // in pair) 
        int u = pq.top().second; 
        pq.pop(); 

        // Get all adjacent of u.  
        for (auto x : adj[u]) { 
            // Get vertex label and weight of current adjacent 
            // of u. 
            int v = x.first; 
            int weight = x.second; 

            // If there is shorted path to v through u. 
            if (dist[v] > dist[u] + weight) { 
                // Updating distance of v 
                dist[v] = dist[u] + weight; 
                pq.push(make_pair(dist[v], v)); 
            } 
        }
    } 

    // Print shortest distances stored in dist[] 
    printf("\nVertex Distance from Source\n"); 
    for (int i = 0; i < V; ++i) 
        printf("%d \t\t %s %d\n", i, "distance: ", dist[i]);
    printf("\n%s %d\n\n", "Distance to destination: ", dist.back());
} 


// Driver program to test methods of graph class 
int main() { 
    const int V = 9;
    vector<iPair> adj[V]; 

    // New edges
    addEdge(adj, 0, 1, 1095);
    addEdge(adj, 0, 6, 715);        // ATL = 0, BOS = 1, DFW = 2,
    addEdge(adj, 0, 3, 844);        // HOU = 3, LAX = 4, NOR = 5,
    addEdge(adj, 0, 5, 499);        // ORD = 6, SFO = 7
    addEdge(adj, 0, 2, 805);
    addEdge(adj, 1, 6, 983);
    addEdge(adj, 1, 2, 1815);
    addEdge(adj, 1, 3, 1886);
    addEdge(adj, 2, 7, 1765);
    addEdge(adj, 2, 4, 1425);
    addEdge(adj, 4, 7, 403);


    // Lookup list
    cout 
    << "ATL = 0, BOS = 1, DFW = 2, \n"
    << "HOU = 3, LAX = 4, NOR = 5, \n"
    << "ORD = 6, SFO = 7" 
    << endl;



    int oac, dac;
    cout << "Origin airport code #: ";
    cin >> oac;
    cout << "Destination airport code #: ";
    cin >> dac;
    dac += 1;

    shortestPath(adj, dac, oac);

    return 0; 
}

Aucun commentaire:

Enregistrer un commentaire