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