CODEWITHSUNDEEP
c++algorithmdijkstra
Jackson Collins
Jackson Collins

Reputation: 120

Dijkstra algorithm C++ Incorrect output

My previous question was answered, but i'm wondering how could i alter this to show the intersections that the lowest route has passed through? Thanks

Note: driverMap is a 2D 14x14 integer vector that holds the distances it takes to get to each vertex

void startFirst(vector< vector<int> > driverMap, vector<Car> allCars, int congestFactor)
{
    clock_t start = clock();
    int Intersections[driverMap.size()];
    int Distances[driverMap.size()];

    for(int i = 0; i < driverMap.size(); i++)
    {
        Intersections[i] = i;
    }

    for(int i = 0; i < driverMap.size(); i++)
    {
        cout << "Intersection '" << i << "': "; 
        for(int k = 0; k < driverMap.size(); k++)
        {
            cout << driverMap[i][k] << "|";
        }
        cout << endl;
    }

    for(int i = 0; i < 1; i++)
    {
        int startInt = allCars[i].getStart();
        Intersections[startInt] = -1;
        Distances[startInt] = 0;

        for (int i = 0; i < driverMap.size(); i++) 
        {
            if(i != startInt)
            {
                Distances[i] = driverMap[startInt][i];
            }
        }

        cout << "FOR INTERSECTION: '" << startInt << "'" << endl;
        cout << endl;

        for (int l = 0; l < driverMap.size(); l++) 
        {
            if(l != startInt)
            {
                Dijkstra(driverMap, Intersections, Distances);
            }
        }

        for (int k = 0; k < driverMap.size(); k++) 
        {
            cout << Distances[k] << "|";
        }
    }
    cout << "Total time simulated: " << (clock() - start ) / (double) CLOCKS_PER_SEC << endl;
}

void Dijkstra(vector< vector<int> > driverMap, int Intersections[], int Distances[]) 
{
    int minValue = 9999;
    int minNode = 0;

    for (int i = 0; i < driverMap.size(); i++) 
    {
        if (Intersections[i] == -1) 
        { 
            continue; 
        }

        if (Distances[i] > 0 && Distances[i] < minValue) 
        {
            minValue = Distances[i];
            minNode = i;
        }
    }

    Intersections[minNode] = -1;

    for (int i = 0; i < driverMap.size(); i++) 
    {
        if (driverMap[minNode][i] < 0) 
        { 
            continue; 
        }

        if (Distances[i] < 0) 
        {
            Distances[i] = minValue + driverMap[minNode][i];
            continue;
        }

        if ((Distances[minNode] + driverMap[minNode][i]) < Distances[i]) 
        {
            Distances[i] = minValue + driverMap[minNode][i];
        }
    }
}

Upvotes: 0

Views: 214

Answers (3)

Keugyeol
Keugyeol

Reputation: 2435

Manual drawing of the graph below backs up the @hk6279's answer. Optimal path to "0" cannot be achieved when arriving from "13". It should either be from "1" or "4" to "0" and as @hk6279 noted and the program correctly computed, the optimal path is "5"-"8"-"4"-"0" of distance 5200.

enter image description here

Upvotes: 3

hk6279
hk6279

Reputation: 1879

Your problem is : Incorrect assumption. Your assumption is incorrect since there is no direct access from 5 to 4.

What you claim is you can get to 0 from 5 is path 5-4-0 with distance 4800 (2600 + 2200). However, the fact is you can only get path 5-8-4-0 by your code with distance 5200 (1500 + 1500 + 2200).

Please be aware that distance 2600 in Intersection 5 is for Intersection 3, not Intersection 4. You are starting with index 0, not 1.

Upvotes: 2

softwarefellow
softwarefellow

Reputation: 11

Refer below for Dijkstra's algorithm in C: http://www.c-program-example.com/2011/10/c-program-to-solve-dijkstras-algorithm.html

Upvotes: -3

Related Questions