ट्रेन का उपयोग करके गंतव्य तक पहुंचने की न्यूनतम लागत

इस समस्या के लिए, एक यात्रा पर N स्टॉप हैं। वाहन स्टॉप 0 से N-1 तक यात्रा शुरू करता है। एक तालिका में सभी स्टेशनों के जोड़े के लिए टिकट लागत दी गई है। हमें उन दी गई लागतों के साथ गंतव्य तक पहुंचने की न्यूनतम लागत ढूंढनी है।

इनपुट और आउटपुट

इनपुट: यात्रा का लागत मैट्रिक्स। 0 15 80 90 ∞ 0 40 50 ∞ ∞ 0 70 ∞ ∞ ∞ 0 आउटपुट: न्यूनतम लागत 65 है। पहले 0 से गंतव्य 1 पर जाएं। (लागत 15), फिर 1 से 4 (लागत 50)। तो कुल लागत 65।

एल्गोरिदम

findMinCost(cost)

इनपुट: प्रत्येक स्रोत से प्रत्येक गंतव्य तक की लागत मैट्रिक्स।

आउटपुट: गंतव्य तक पहुंचने की न्यूनतम लागत ढूंढें।

शुरू     costLoc नामक सरणी परिभाषित करें, जिसका आकार स्थानों की संख्या के समान है,     costLoc को ∞ से भरें।     n := स्थानों की संख्या     costLoc[0] := 0     प्रत्येक स्रोत i से प्रत्येक गंतव्य j के लिए, करें       यदि costLoc[j] > costLoc[i] + cost[i, j], तो         costLoc[j] := costLoc[i] + cost[i, j]       किया     costLoc[n-1] वापस करें अंत

उदाहरण

#include<iostream> #define INF INT_MAX #define NODE 4 using namespace std; int cost[NODE][NODE] = {     {0, 15, 80, 90},     {INF, 0, 40, 50},     {INF, INF, 0, 70},     {INF, INF, INF, 0} }; int findMinCost() {         //गंतव्य तक पहुंचने की सबसे छोटी संभव लागत खोजें     int costStation[NODE];       //किसी भी स्टेशन तक पहुंचने की लागत 0 से संग्रहीत करें     for (int i=0; i costStation[i] + cost[i][j])       //न्यूनतम लागत के लिए मध्यवर्ती स्टेशन खोजें costStation[j] = costStation[i] + cost[i][j];     return costStation[NODE-1]; } int main() {     cout << "The Minimum cost to reach station " << NODE << " is " << findMinCost() << endl;     return 0; }

आउटपुट

The Minimum cost to reach station 4 is 65