C++ Dijkstra's algorithm program with initial vertices problem and resulting one less vertex

Question

I'm working on C++ representation/implementation of Dijkstra's algorithm and I found this program online which fails to execute properly on TurboC++. Any one know the solution? I also want to know why there is a minimum value of 31999 and the coding runs on a mobile emulator but refuses to run on PC TurboC++

#include<iostream.h>
#include<conio.h>
#include<stdio.h>
//using namespace std;
int shortest(int, int);
int cost[10][10], dist[20], i, j, n, k, m, S[20], v, totcost, path[20], p;
int main()
{
    int c;
    cout << "enter no of vertices";
    cin >> n;
    cout << "enter no of edges";
    cin >> m;

    cout << "\nenter\nEDGE Cost\n";
    for (k = 1; k <= m; k++)
    {
        cin >> i >> j >> c;
        cost[i][j] = c;
    }

    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            if (cost[i][j] == 0)
                cost[i][j] = 31999;

    cout << "enter initial vertex";
    cin >> v;
    cout << v << "\n";
    shortest(v, n);
}

int shortest(int v, int n)
{
    int min;
    for (i = 1; i <= n; i++)
    {
        S[i] = 0;
        dist[i] = cost[v][i];
    }
    path[++p] = v;
    S[v] = 1;
    dist[v] = 0;
    for (i = 2; i <= n - 1; i++)
    {
        k = -1;
        min = 31999;
        for (j = 1; j <= n; j++)
        {
            if (dist[j] < min && S[j] != 1)
            {
                min = dist[j];
                k = j;
            }
        }

        if (cost[v][k] <= dist[k])
            p = 1;
        path[++p] = k;

        for (j = 1; j <= p; j++)
            cout << path[j];
        cout << "\n";
        //cout <<k;
        S[k] = 1;
        for (j = 1; j <= n; j++)
            if (cost[k][j] != 31999 && dist[j] >= dist[k] + cost[k][j] && S[j] != 1)
                dist[j] = dist[k] + cost[k][j];
    }
}

Arrays are 0 based so all the loops from 1 to <= n are suspect. — Richard Critten, Oct 09 '18 at 08:20
Formatting, consistent indentation, spacing, comments and descriptive variable names are not needed by the compiler, but it *is* needed for humans attempting to read and understand your code. Please try to reformat your code to make it more readable. — Some programmer dude, Oct 09 '18 at 08:20
Also note that if you're using `` then you're learning a very old version of C++, one from before it was standardized in 1998. If you want to learn modern C++ then please [get a few good books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list/388282#388282), and find a modern up-to-date environment and compiler. Even if your school forces you to use an old environment and old C++, learn modern C++ using modern tool on your own. — Some programmer dude, Oct 09 '18 at 08:22
@RichardCritten thank you for pointing that. so what should i change? — Karthikcbe, Oct 09 '18 at 08:24
Is there any requirement to do this in Turbo C++? If not, I recommend that you ditch it post-haste and go with a more recent implementation instead. — Blaze, Oct 09 '18 at 08:29
@Blaze that's the problem. i have to make it work on turbo c++ , this is a lab program. — Karthikcbe, Oct 09 '18 at 08:32
About the minimum: the usual idiom for finding a minimum is initialize min to something large, if you find a lower value, set the current minimum to that. So what is 31999? In TurboC++ you probably have 16-bit ints that go from -32768 to +32767, so 31999 is close to the maximum value. — , Oct 09 '18 at 09:43

score 2 · Accepted Answer · answered Oct 09 '18 at 08:37

2

Arrays are 0 based so all the loops from 1 to <= n are suspect.

answered Oct 09 '18 at 08:37

C++ Dijkstra's algorithm program with initial vertices problem and resulting one less vertex

1 Answers1